KMP法のお勉強
だが解説は面倒なのでしない。
maketableさえ覚えればsearchはそれと形が似ているので簡単そう。
#include <cstdio> void kmp_maketable(const char *key, int *table) { table[0]=-1;table[1]=0; int i=2,j=0; while(i==0 || key[i-1]) { if(key[i-1] == key[j]) { table[i++] = ++j; } else if(j>0) { j = table[j]; } else { table[i++] = 0; } } } void simple_search(const char *str, const char *key) { for(int i = 0; str[i]; i++) { int j; for(j = 0; str[i+j] && key[j] && str[i+j]==key[j]; j++) { } if(!key[j]) { printf("A: %d\n", i); } } } void kmp_search(const char *str, const char *key, const int *table) { int i=0,j=0; while(str[i]) { if(str[i]==key[j]) { if(!key[j+1]) { printf("B: %d\n", i-j); } i++, ++j; } else if(j>0) { j = table[j]; } else { i++; } } } int main(int argc, char **argv) { const char *str = "ABCABCABCDABCABCDABCBCABCABCDABC"; const char *key = "ABCABCDABC"; int table[100]; simple_search(str, key); kmp_maketable(key, table); kmp_search(str, key, table); return 0; }