c - 长文本字符串中的模式匹配

Question

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

适用于:字符串:ishanthakkar ishan模式:ishan

但它失败了:

字符串:cpr 编程啪嗒声: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;
}

Answer 1

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() pattern 和 target 在调用 kmp() 之前(以及在 scanf() 之后)

chomp(target);
chomp(pattern);

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

程序应该表现得更好。

---

注意:10是'\n'(LF)，13是'\r'( Chrome )