Соответствие шаблону в длинной текстовой строке

Я написал этот код, и он работает в некоторых случаях. Иногда, однако, это терпит неудачу, и я просто не понимаю, почему. Может кто-то, пожалуйста, помогите мне обнаружить ошибку?Соответствие шаблону в длинной текстовой строке

Он работает: Строка: 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; 
}

// Th это строка поиска соответствия функции в O (n) времени, поэтому повторяйте ее через текстовую строку только один раз, когда обнаружен символ unmatching; он приступить к следующему символу и начать по сравнению с первым символом строки для поиска т.е. картины

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; 
}

источник

2013-06-10 Programming_crazy

Попробуйте правильно сделать код отступа - не нужно лишних пробелов. –

Можете ли вы прокомментировать свой код так, чтобы цель различных частей была ясна? Насколько я знаю, функция типа 'kmp()' не является частью стандартного лексикона вычислений, и вы только заявляете, что программа выполняет «сопоставление шаблонов», даже не указав, что это значит. Насколько нам известно, код может быть правильным, как указано. –

@ John: Извините за неудобства, я добавил небольшое описание, чтобы понять программу. На самом деле, я не кодировал всю программу, поэтому у меня также есть путаница! –

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-10 15:12:42

Что такое 10 и 13 здесь? –

10 является CR, 13 является LF –

Я, хотя это должно работать! Я попытался удалить CR LF, но в этом случае он не работает ни в одном из случаев! –

Гот подсказка:

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

проходил длина строки + 1 (для нулевого символа), так что было давая ложный результат для некоторой текстовой строки

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

работает для всех случаев!

Спасибо всем вам за ваше время!

источник

2013-06-11 05:43:46

Соответствие шаблону в длинной текстовой строке

ответ

Смежные вопросы