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的实现方法，你看一下：

1. public class KMP
   
2. {
   
3.         public static int[] preProcess(char[] B)
   
4.         {
   
5.                 int size = B.length;
   
6.                 int[] P = new int[size];   //给模式匹配串添加一个P数组
   
7.                 P[0] = 0;                  //也将就是KMP算法中非著名的next数组
   
8.                 int j = 0;                 //它指导者模式匹配串下一步改用第几号元素去进行匹配
   
9. 
   
10.                 for (int i=1; i < size; i++ )   //j为前缀标号  i为后缀标号
    
11.                 {
    
12.                         while (j>0 && B[j] != B[i] )
    
13.                         {
    
14.                                 j = P[j];
    
15.                         }
    
16.                         if (B[j] == B[i])
    
17.                         {
    
18.                                 j++;
    
19.                         }
    
20.                         P[i] = j;
    
21.                 }
    
22.                 return P;
    
23.         }
    
24. 
    
25.         public static void kmp(String parStr, String subStr )   //kmp算法的实现
    
26.         {
    
27.                 int subSize = subStr.length();   //子串
    
28.                 int parSize = parStr.length();   //主串
    
29.                 char[] B = subStr.toCharArray();
    
30.                 char[] A = parStr.toCharArray();
    
31.                 int[] P = preProcess(B);
    
32.                 int j = 0;
    
33.                 int k = 0;
    
34. 
    
35.                 for (int i=0; i < parSize; i++ )
    
36.                 {
    
37.                         while (j > 0 && B[j] != A[i] )
    
38.                         {
    
39.                                 j = P[j-1];
    
40.                         }
    
41. 
    
42.                         if (B[j] == A[i])
    
43.                         {
    
44.                                 j++;
    
45.                         }
    
46. 
    
47.                         if (j == subSize)
    
48.                         {
    
49.                                 j = P[j-1];
    
50.                                 k++;
    
51.                                 System.out.printf("Find subString '%s' at %d\n", subStr, i-subSize+1);
    
52.                         }
    
53.                 }
    
54.                 System.out.printf("Totally found %d times for '%s'.\n\n", k, subStr);
    
55.         }
    
56.         public static void main(String args[])
    
57.         {
    
58.                 kmp("abcdeg, abcdeh, abcdef!", "abcdef");
    
59. 
    
60.                 kmp("测试汉字的匹配，小白马","小白马");
    
61.         }
    
62. }

复制代码

章伯魂

因为若不存在，则返回 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了