关于字符串算法KMP的代码问题?

peterJXL
  • 29

2022-2-28补充:已解决,感谢 brokkr,大佬讲的很详细了。谢谢各位。

原提问:
本人最近在复习数据结构-kmp算法的时候,在自己写程序的时候发现一直得不到想要的结果,经过debug,
1.在while循环里判断为true,但还是结束了循环,看了书籍和思否上面的文章也百思不得其解,代码基本是一样的
2.用Java实现就没这个问题??
本人是自己写的代码,和思否上的比较过也没看出有什么区别:KMP 算法 - SegmentFault 思否: https://segmentfault.com/a/11...

各位大佬能不能帮忙看看,如果需要远程我也可以提供!谢谢!

2022-2-24版代码 C++

#include<stdio.h>
#include "string.h"
void getNext(char T[], int next[]){
    int i=0, j=-1;
    next[0] = -1;
    while ( i < strlen(T) ){
        if( -1 == j || T[i] == T[j]){
            //分两种情况,一种是j== -1,说明没找到更小的前缀和后缀,需要从头开始比较,next[i] =0。
            // 另一种是前缀和后缀相等,则匹配值+1
            i++;
            j++;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

int kmp(char S[], char T[]){  //S是主串,T是模式串
    int next[strlen(T)];
    getNext(T, next);
    int i = 0, j = 0;
    while (  i < strlen(S) && j < strlen(T) ){
        if ( -1 == j || S[i] == T[j]){
            i++;
            j++;
        } else{
            j = next[j];
        }
    }

    if(strlen(T) == j)
        return i - j;
    else
        return -1;
}

int main()
{
    char S[80],T[80];
    gets(S);
    gets(T);
    printf("%d", kmp(S, T));
}

使用的测试案例:主串jfaweiof, 子串of,在第二次循环的时候就直接结束了循环,然而i和j的值都是小于主串和模式串的值的,百思不得其解:
代码运行
代码运行

debug窗口:i = 0, j=-1,而且while循环的判断的结果都是true,为何就会结束循环呢??
debug窗口

本地环境:win10 64位,Clion版本号为2021.3.2 mingw用的是Clion内置的
image.png

也考虑过是不是短路问题,写了以下代码进行测试,也确实执行了11次;

int i = 0;
    while (0 < 3 && -1 < 3){
        printf("???\n");
        i++;
        if(i > 10)
            break;
    }

2022-2-26版代码,C++
经朋友提醒,存在求next数组时越界的情况,已修复,将求next数组的while条件 从 为 i < strlen(T) 改为 i < strlen(T) -1
但还是在kmp函数里第一次循环就结束了

#include<stdio.h>
#include "string.h"
void getNext(char T[], int next[]){
    int i=0, j=-1;
    next[0] = -1;
    while ( i < strlen(T) -1 ){
        if( -1 == j || T[i] == T[j]){
            //分两种情况,一种是j== -1,说明没找到更小的前缀和后缀,需要从头开始比较,next[i] =0。
            // 另一种是前缀和后缀相等,则匹配值+1
            i++;
            j++;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

int kmp(char S[], char T[]){
    int next[strlen(T)];
    getNext(T, next);
    int i = 0, j = 0;
    while (  i < strlen(S) && j < strlen(T) ){
        if ( -1 == j || S[i] == T[j]){
            i++;
            j++;
        } else{
            j = next[j];
        }
    }

    if(strlen(T) == j)
        return i - j;
    else
        return -1;
}

int main()
{
    char S[80],T[80];
    gets(S);
    gets(T);
    printf("%d", kmp(S, T));
}

但是用Java实现,就没这个问题,百思不得其解

package com.peterjxl.string;

import java.util.Scanner;

public class KMP {

    public static void getNext(char[] T, int[] next){
        int i = 0, j = -1;
        next[0] = -1;
        while ( T.length -1 > i){

            if( -1 == j || T[i] == T[j]){
                ++i;
                ++j;
                next[i] = j;
            }else {
                j = next[j];
            }
        }
    }

    public static int KMP(char[] S, char[] T){
        int[] next = new int[T.length];
        getNext(T, next);
        int i=0, j=0;
        while (S.length > i && T.length > j){
            if(-1 == j || S[i] == T[j]){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if(T.length == j)
            return i-j;
        else
            return -1;
    }

    public static void main(String[] args) {
        String S, T;
        Scanner input = new Scanner(System.in);
        S = input.nextLine();
        T = input.nextLine();
        System.out.println(KMP(S.toCharArray(), T.toCharArray()));
    }
}
回复
阅读 525
1 个回答
✓ 已被采纳

你的代码这一行

while (  i < strlen(S) && j < strlen(T) ){

编译的时候编译器会警告你,说无符号变量不能跟有符号变量进行比较,但你一定忽略了。
你的 j 在第二轮循环的时候是 -1 而 strlen(T) 返回的是个无符号的值,编译器把 -1 当作0xFFFFFFFF 来处理,当然就结束循环了。
代码改成

while (  i < (int)strlen(S) && j < (int)strlen(T) ){

就可以了。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏