という気がしてきたので、文字列検索の有限オートマトン化をしてみた。 …普通にこれでいいじゃん! 有限オートマトンの生成にかかる時間およびメモリはn=キーサイズ,c=文字の種類とおいてO(cn)なので、そこで少し遅れをとるけど、検索が非常にシンプルで高速(検索対象文字列を一回しか参照しない)になる。 検索文字列が小さくて、検索対象文字列が大きいときに有効だと思う。 #include <cstdio> 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