#include <stdio.h>
#define MAX_LEN 100
int f[MAX_LEN];
// Compute failure function
void compute_failure_function(char* b, int n) {
int t, s;
t = 0;
f[0] = 0;
for (s = 0; s < n -1; s++) {
while (t > 0 && b[s+1] != b[t])
t = f[t-1];
if (b[s+1] == b[t]) {
t++;
f[s+1] = t;
} else {
f[s+1] = 0;
}
}
}
// Match keyword
int match_keyword(char* a, int m, char* b, int n) {
int s, i;
s = 0;
for (i = 0; i <= m-1; i++) {
while (s > 0 && a[i] != b[s])
s = f[s-1];
if (a[i] == b[s])
s++;
if (s == n)
return i;
}
return -1;
}
void info_failure_function(int n) {
int i;
printf("----------------------------\n");
printf("Failure Function \n");
printf("----------------------------\n");
printf("s |");
for (i = 0; i < n; i++)
printf("%3d", i);
printf("\n");
printf("f(s) |");
for (i = 0; i < n; i++)
printf("%3d", f[i]);
printf("\n");
printf("----------------------------\n");
}
void info_matched_keyword(char* a, int n, int end, char*b ) {
if (end < 0) {
printf("NO MATCH\n");
return;
}
printf("%s\n", a);
int i;
int begin;
begin = end -n + 1;
for (i = 0; i < begin; i++)
printf(" ");
for (i = begin; i <= end; i++)
printf("%c", b[i - begin]);
printf("\n");
}
void kmp(char* a, int m, char* b, int n) {
int end;
compute_failure_function(b, n);
info_failure_function(n);
end = match_keyword(a, m, b, n);
info_matched_keyword(a, n, end, b);
}
int main(int argc, const char *argv[]) {
kmp("abababaab", 9, "ababaa", 6);
kmp("abababbaa", 9, "ababaa", 6);
return 0;
}
分享到:
相关推荐
Knuth-Morris-Pratt algorithm
KMPAlgorithm.c
字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”...许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。
这是一个关于字符串匹配的kmp算法,程序简单精炼,可以借鉴一下
kmp算法kmp-algorithm-master.zip
KMP算法 字符串匹配算法 The KMP algorithm string matching algorithm
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
KMP algorithm for matching string problem
kmp算法,kmp-algorithm-master (1).zip
parrallel computing string with kmp algorithm
The classical KMP algorithm for string matching (the target string can be modified in the main function, if any match is found, the matching position would be returned)
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
KMP for string matching
KMP(Knuth-Morris-Pratt)算法是一种改进的字符串匹配算法,用于在一个文本字符串(T)中查找一个词(W)的出现位置。KMP算法的核心在于当字符串匹配发生不一致时,能知道已经部分匹配这个有效信息,利用这个信息...
KMP算法的一个经典题题解,
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
克努斯-莫里斯-普拉特算法,KMP算法(Knuth–Morris–Pratt algorithm) 一种字符串查找算法。在一个“主文本字符串” S 内查找一个“词” W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来...
KMP算法(Knuth-Morris-Pratt Algorithm)是一种改进的字符串匹配算法,由D.E.Knuth、J.H.Morris和V.R.Pratt提出。该算法的核心思想是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数,以达到快速匹配的目的...
StringMatch:这是Randomized Algorithm类的最终项目。 基本比较了朴素算法,Rabin-Karp算法和KMP算法的性能