4

我编写了这段代码，它在某些情况下有效。然而，有时它会失败，我就是不明白为什么。有人可以帮我找出错误吗？

它适用于：字符串：ishanthakkar ishan 模式：ishan

但它失败了：

字符串：cpr ograming 模式：cpr

资源：

#include <stdio.h>    
#include <stdlib.h>    
#include <string.h>

int *compute_prefix_function(char *pattern, int psize)
{
    int k = -1;
    int i = 1;
    int *pi = malloc(sizeof(int)*psize);
    if (!pi)
        return NULL;

    pi[0] = k;
    for (i = 1; i < psize; i++) {
        while (k > -1 && pattern[k+1] != pattern[i])
            k = pi[k];
        if (pattern[i] == pattern[k+1])
            k++;
        pi[i] = k;
    }
    return pi;
}

// 这个函数在 O(n) 时间内找到匹配的字符串，所以当找到不匹配的字符时，只遍历文本字符串一次；它继续下一个字符并开始与要搜索的字符串的第一个字符进行比较，即模式

int kmp(char *target, int tsize, char *pattern, int psize)
{
    int i;
    int *pi = compute_prefix_function(pattern, psize);
    int k = -1;
    if (!pi)
        return -1;

    for (i = 0; i < tsize; i++) {
        while (k > -1 && pattern[k+1] != target[i])
            k = pi[k];
        if (target[i] == pattern[k+1])
            k++;

        if (k == psize - 1) {
            free(pi);
            return i-k;
        }
    }

    free(pi);
    return -1;
}

int main(int argc, const char *argv[])
{
    char target[200];
    char *ch = target;
    char pattern[20];
    int i;

    printf("Enter the string: \n");
    fgets(target,100,stdin);

    printf("Enter the string to be matched: \n");
    fgets(pattern,20,stdin);

    i = kmp(target, strlen(target), pattern, strlen(pattern)); 
    if (i >= 0)
        printf("matched @: %s\n", ch + i);

    getch();
    return 0;
}
4

2 回答 2

2

fgets函数读取并在字符串中包含结尾的 CR（或 CRLF）。

添加一个chomp()函数，比如

void chomp(char *s) {
    int n = strlen(s);
    while (n && (s[n-1]==10 || s[n-1]==13)) s[--n] = 0;
}

删除字符串末尾的任何 CR 或 LF。
然后在调用之前（和之后）进行chomp() 模式和目标kmp()scanf()

chomp(target);
chomp(pattern);

i = kmp(target, strlen(target), pattern, strlen(pattern));

该程序应该表现得更好。

注：10是'\n'(LF) 和13是'\r'(CR)

于 2013-06-10T15:12:42.787 回答
1

得到线索：

i = kmp(target, strlen(target), pattern, strlen(pattern));

正在传递字符串长度+1（对于空字符），因此它为某些文本字符串提供了错误的结果

i = kmp(target, strlen(target)-1, pattern, strlen(pattern)-1);

适用于所有情况！

感谢大家的时间！

于 2013-06-11T05:43:46.780 回答