http://mindlee.com/2011/11/25/string-matching/
http://www.cnblogs.com/nullzx/p/7499397.html
http://www.matrix67.com/blog/archives/115
https://github.com/topics/string-search
http://blog.csdn.net/zhongwen7710/article/details/39274349
/* 运行结果: _________________________ 朴素算法,匹配位置是:7 */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; //朴素匹配算法 void NativeStringMatcher(const char *T, const char *P) { int n = strlen(T); int m = strlen(P); for (int j, i = 0; i < n - m; i++) { for (j = 0; j < m; j++) { if (T[i + j] != P[j]) { break; } } if (j == m) { printf("朴素算法,匹配位置是:%d\n", i + 1); } } } int main() { const char *T = "2359023141526739921"; const char *P = "31415"; NativeStringMatcher(T, P); return 0; }
/* 运行结果: _________________________ t1 = 8 t2 = 9 t3 = 3 t4 = 11 t5 = 0 t6 = 1 t7 = 7 匹配位置是:7 t8 = 8 t9 = 4 t10 = 5 t11 = 10 t12 = 11 t13 = 7 伪命中点:13 t14 = 9 */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; //朴素匹配算法,用于RabinKarp调用 bool NativeStringMatcher(const char *T, const char *P) { int n = strlen(T); int m = strlen(P); for (int j, i = 0; i < n - m; i++) { for (j = 0; j < m; j++) { if (T[i + j] != P[j]) { break; } } if (j == m) { return true; } } return false; } //RabinKarp算法 void RabinKarp(const char *T, const char *P, int d, int q) { int n = strlen(T); int m = strlen(P); int h = 1; for (int i = 0; i < m - 1; i++) { h *= d;//pow可能会越界,所以用乘法 if (h >= q) { h %= q; } } int p = 0; int t = 0; for (int i = 0; i < m; i++) { p = (d * p + (P[i] - '0')) % q; t = (d * t + (T[i] - '0')) % q; } for (int i = 0; i < n - m; i++) { printf("t%d = %d\n", i + 1, t); if (p == t) { if (NativeStringMatcher(T + i, P)) { printf("匹配位置是:%d\n", NativeStringMatcher(T + i, P) + i); } else { printf("伪命中点:%d\n", i + 1); } } if (i < n - m) { t = (d * (t - h * (T[i] - '0')) + T[i + m] - '0') % q; if (t < 0) { t += q; } } } } int main() { const char *T = "2359023141526739921"; const char *P = "31415"; RabinKarp(T, P, 10, 13); return 0; }
/* 运行结果: ———————————————— 匹配位置: 1 匹配位置: 12 */ #include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; //伪代码中的fail数组,用fail来表示 int fail[1000]; //预处理fail数组 void ComputePrefixFunction(char *P) { int m = strlen(P); memset(fail, 0, sizeof(fail)); fail[0] = 0; int k = 0; for (int i = 2; i <= m; i++) { while (k > 0 && P[k] != P[i - 1]) { k = fail[k - 1]; } if (P[k] == P[i - 1]) { k = k + 1; } fail[i - 1] = k; } } void KMPMatcher(char *T, char *P) { int n = strlen(T); int m = strlen(P); int q = 0; for (int i = 1; i <= n; i++) { while (q > 0 && P[q] != T[i - 1]) { q = fail[q - 1]; } if(P[q] == T[i - 1]) { q = q + 1; } if(q == m) { printf("匹配位置: %d\n", i - m + 1); q = fail[q - 1]; } } } int main() { KMPMatcher("123451233211234561234", "12345"); return 0; }
//HDU 1251 代码,字典树模板 #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; const int MAXN = 100010, MAXM = 11, KIND = 26; //小写字母->26 ,大小混写->52,大小写+数字->62 int m; struct node { char* s; int prefix; bool isword; node* next[KIND]; void init() { s = NULL; prefix = 0;//前缀 isword = false; memset(next, 0, sizeof(next)); } }a[MAXN*MAXM], *root;//根 void insert(node *root, char *str) {//插入 node *p = root; for (int i = 0; str[i]; i++) { int x = str[i] - 'a'; p->s = str + i; if (p->next[x] == NULL) { a[m].init(); p->next[x] = &a[m++]; } p = p->next[x]; p->prefix++; } p->isword = true; } bool del(node *root, char *str) {//删除 node *p = root; for (int i = 0; str[i]; i++) { int x = str[i] - 'a'; if (p->next[x] == NULL) { return false; } p = p->next[x]; }//for(i) if (p->isword) { p->isword = false; } else { return false; } return true; } bool search(node *root, char* str) {//查找 node* p = root; for (int i = 0; str[i]; i++) { int x = str[i] - 'a'; if (p->next[x] == NULL) { return false; } p = p->next[x]; }//for(i) return p->isword; } int count(node *root, char *str) {//统计后缀 node *p = root; for (int i = 0; str[i]; i++) { int x = str[i] - 'a'; if (p->next[x] == NULL) { return 0; } p = p->next[x]; }//for(i) return p->prefix; } int main() { m = 0; a[m].init(); root = &a[m++]; char str[MAXM]; while (gets(str), strcmp(str, "")) { insert(root, str); } while (gets(str)) { printf("%d\n", count(root,str)); } }
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; #define MAXN 10001 #define MAXM 51 #define KIND 26 struct node { int prefix; node *fail; node *next[26]; void init() { prefix = 0; fail = NULL; memset(next, 0, sizeof(next)); } }*que[MAXN * MAXM], trie[MAXN * MAXM], *root; int cnt; char keyword[MAXM]; char str[MAXN * 2]; void Insert(node *root, char *str) { node *ptr = root; for (int i = 0; str[i]; i++) { int x = str[i] - 'a'; if (ptr->next[x] == NULL) { trie[cnt].init(); ptr->next[x] = &trie[cnt++]; } ptr = ptr->next[x]; } ptr->prefix++; }//insert void Build(node *root) { int head = 0, tail = 0; root->fail = NULL; que[head++] = root; while (head != tail) { node *tmp = que[tail++]; node *ptr = NULL; for (int i = 0; i < KIND; i++) { if (tmp->next[i] != NULL) { if (tmp == root) { tmp->next[i]->fail = root; } else { ptr = tmp->fail; while (ptr != NULL) { if (ptr->next[i] != NULL) { tmp->next[i]->fail = ptr->next[i]; break; } ptr = ptr->fail; } if (ptr == NULL) { tmp->next[i]->fail = root; } }//if_else que[head++] = tmp->next[i]; }//if }//for(i) }//while (head != tail) }//Build int Query(node *root, char *str) { int ret = 0; node *ptr = root; for (int i = 0; str[i]; i++) { int x = str[i] - 'a'; while (ptr->next[x] == NULL && ptr != root) { ptr = ptr->fail; } ptr = ptr->next[x]; if (ptr == NULL) { ptr = root; } node *tmp = ptr; while (tmp != root && tmp->prefix != -1) { ret += tmp->prefix; tmp->prefix = -1; tmp = tmp->fail; } }//for(i) return ret; } int main() { int cas, n; scanf("%d", &cas); while (cas--) { // head = tail = 0; cnt = 0; trie[cnt].init(); root = &trie[cnt++]; scanf("%d%*c", &n); while (n--) { gets(keyword); Insert(root, keyword); } Build(root);//构造自动机 scanf("%s", str); printf("%d\n", Query(root, str)); } return 0; }