论坛 › 数据结构与算法 › KMP算法按照小甲鱼的算法加的主函数输出一直是0，求答疑

23Aaron 发表于 2014-7-15 18:10:51

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

#include <stdio.h>

typedef char* String;

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

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

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

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

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

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

青玄 发表于 2014-7-18 17:47:04

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

                for (int i=1; i < size; i++ )   //j为前缀标号i为后缀标号
                {
                        while (j>0 && B != B )
                        {
                                j = P;
                        }
                        if (B == B)
                        {
                                j++;
                        }
                        P = 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 != A )
                        {
                                j = P;
                        }

                        if (B == A)
                        {
                                j++;
                        }

                        if (j == subSize)
                        {
                                j = P;
                                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("测试汉字的匹配，小白马","小白马");
        }
}

章伯魂 发表于 2014-8-12 21:07:21

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

whdd 发表于 2019-4-22 12:51:08

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

枣子哥006 发表于 2019-12-23 23:06:30

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

那该怎样改

代码爱我 发表于 2020-2-5 12:49:25

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

SmithDimon 发表于 2020-3-19 18:26:33

本帖最后由 SmithDimon 于 2020-3-19 19:56 编辑

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

查看完整版本: KMP算法按照小甲鱼的算法加的主函数输出一直是0，求答疑