KMP算法按照小甲鱼的算法加的主函数输出一直是0，求答疑

23Aaron

#include <stdio.h>

typedef char* String;

void get_next( String T, int *next )
{
        int j = 0;
        int i = 1;
        next[1] = 0;

        while( i < T[0] )
        {
                if( 0 == j || T[i] == T[j] )
                {
                        i++;
                        j++;
                        if( T[i] != T[j] )
                        {
                                next[i] = j;
                        }
                        else
                        {
                                next[i] = next[j];
                        }
                }
                else
                {
                        j = next[j];
                }
        }
}

// 返回子串T在主串S第pos个字符之后的位置
// 若不存在，则返回0
int Index_KMP( String S, String T, int pos )
{
        int i = pos;
        int j = 1;
        int next[255];

        get_next( T, next );
       
        while( i <= S[0] && j <= T[0] )
        {
                if( 0 == j || S[i] == T[j] )
                {
                        i++;
                        j++;
                }
                else
                {
                        j = next[j];
                }
        }

        if( j > T[0] )
        {
                return i - T[0];
        }
        else
        {
                return 0;
        }
}

int main()
{
        char s[255]="7abcdefg";
        char t[255]="2cd";
        int k;
        k=Index_KMP(s,t,1);
        printf("%d",k);
}

青玄

这是JAVA的实现方法，你看一下：

public class KMP
{
        public static int[] preProcess(char[] B)
        {
                int size = B.length;
                int[] P = new int[size];   //给模式匹配串添加一个P数组
                P[0] = 0;                  //也将就是KMP算法中非著名的next数组
                int j = 0;                 //它指导者模式匹配串下一步改用第几号元素去进行匹配

                for (int i=1; i < size; i++ )   //j为前缀标号  i为后缀标号
                {
                        while (j>0 && B[j] != B[i] )
                        {
                                j = P[j];
                        }
                        if (B[j] == B[i])
                        {
                                j++;
                        }
                        P[i] = j;
                }
                return P;
        }

        public static void kmp(String parStr, String subStr )   //kmp算法的实现
        {
                int subSize = subStr.length();   //子串
                int parSize = parStr.length();   //主串
                char[] B = subStr.toCharArray();
                char[] A = parStr.toCharArray();
                int[] P = preProcess(B);
                int j = 0;
                int k = 0;

                for (int i=0; i < parSize; i++ )
                {
                        while (j > 0 && B[j] != A[i] )
                        {
                                j = P[j-1];
                        }

                        if (B[j] == A[i])
                        {
                                j++;
                        }

                        if (j == subSize)
                        {
                                j = P[j-1];
                                k++;
                                System.out.printf("Find subString '%s' at %d\n", subStr, i-subSize+1);
                        }
                }
                System.out.printf("Totally found %d times for '%s'.\n\n", k, subStr);
        }
        public static void main(String args[])
        {
                kmp("abcdeg, abcdeh, abcdef!", "abcdef");

                kmp("测试汉字的匹配，小白马","小白马");
        }
}

章伯魂

因为若不存在，则返回 0，"7abcdefg"里没有"2cd";

whdd

按你那样设置，j永远不可能大于T0

枣子哥006

whdd 发表于 2019-4-22 12:51
按你那样设置，j永远不可能大于T0

那该怎样改

代码爱我

char t[255]="2cd"中t[0]实际上是50，因为2的ASCII码是５０

SmithDimon

准却来说就是ASCII码的问题
你只要在你定义完字符串后加上
s[0]=s[0]-48;
t[0]=t[0]-48;
就Ok了