Kmpアルゴリズムのまとめ

11788 ワード

Kmpアルゴリズムは実用的な高速文字列マッチングアルゴリズムである.
1.文字列一致とは?
文字列マッチングとは、文字列sにおいて文字列tを検索することである.
2.照合方法
文字列sを主列とし、長さはnである.文字列tはモード列、長さmであり、主列でモード列を検索する方法を考慮する.
まず暴力の方法を考えて、暴力for主列の中の各位置について、各位置について再びモード列の中の各位置について、一致できるかどうか、時間複雑度O(nm)を見てみましょう.
3.Kmpアルゴリズムの本質
暴力的なアルゴリズムでは,主列の各位置に文字列マッチングを行ったが,マッチングのたびにパターン列をスキャンし,時間の浪費を招いた.プライマリ・ストリングの各位置について、不一致後にマッチング可能な位置をすばやく見つけてマッチングを続行できる場合は、マッチングの速度を速めることができます.(理解できない?次の例を見てください.)
主列:abaababa
パターン列:ababa
一致する場合は、まず1番の位置から一致します
a b a a b a a b a b a
|   | | x
a b a b a
マッチングができないことがわかりました.ビット移動を必要とせず、マッチング可能な位置を直接見つけてマッチングします.
a b a a b a a b a b a
| x
a b a b a
一致しないことを発見してから移動します
a b a a b a a b a b a
|   | | x
a b a b a
再移動
a b a a b a a b a b a
|   x
a b a b a
移動
a b a a b a a b a b a
    |   | | |   |
a b a b a
一致することを発見し、答えを得る.
マッチング時にマッチングを継続できない場合,モード列の位置を移動することによって,位置に移動する最長接尾辞が元の位置の最長接頭辞に等しくなり,Kmpの奥義はこの移動を処理する方法にあることを見出した.
4.Kmpの実現方法
Kmpは処理移動時にnext配列を導入し,next[i]はi位置と最長接尾辞を持つ最長接頭辞を表す.そういえば少し回りますが、例のパターン列ababaを見てみましょう.next[1]=0, next[2]=0, next[3]=1, next[4]=2, next[5]=3.next配列は、位置i(iを含まない)の接頭辞における接頭辞と接尾辞の最も長い共通部分と見なすこともできる.next[4]を例にとると、位置4の接頭辞はababであり、その接頭辞と接尾辞の最長共通部分はabであり、長さは2であるため、next[4]は2である.
ではnext配列はどのように求めるべきか、まず以下のnext配列を求める方法を見てみましょう.

1 void getnext(void) {
2     next[1]=0;
3     int k=0;
4       for (int i=2;i<=m;++i) {
5           while (k>0 && t[i]!=t[k+1]) k=next[k];
6           if (t[i]==t[k+1]) k++;
7           next[i]=k;
8       }
9 }

next[i]は、iの位置を含む接頭辞のうち、接頭辞と接尾辞の最長共通部分を表すが、next[1]は1の位置を含まないため、0である.kは接頭辞と接尾辞の最長共通部分(レベルnextの値)を記録し,その後next[i]の値については繰返しにより得ることができる.現在の位置がiである、現在の位置が前のnext値+1と一致可能であれば、現在のnext値は前の値+1となる.現在の一致ができない場合、k=next[k]は、k位置の最長接頭辞のうち接頭辞と接尾辞の最長共通部分がnext[k]であるため、next[k]もi位置の最長接頭辞と接尾辞の共通部分である.whileが探索した後,現在の位置がk+1の位置と等しいか否かを判断すると,現在のnext値が得られる.△理解しにくいということは、データを使って手動でシミュレーションすることで、だんだん理解できるようになりました.

next配列を求める方法を話したが,最も重要なマッチングはまだ言っていない.では、どのように一致するか、コードを見てみましょう.

 1 void getnext(void) {
 2     next[1]=0;
 3     int k=0;
 4       for (int i=2;i<=m;++i) {
 5         while (k>0 && t[i]!=t[k+1]) k=next[k];
 6         if (t[i]==t[k+1]) k++;
 7         next[i]=k;
 8       }
 9 }
10 
11 void kmp(void) {
12     int k=0;
13       for (int i=1;i<=n;++i) {
14           while (k>0 && s[i]!=t[k+1]) k=next[k];
15           if (s[i]==t[k+1]) k++;
16           if (k==m) {
17               printf("%d ",i-k+1);
18           }
19       }
20 }

next配列を求めるときと似ていますか?実際にnext配列を求めるのはモード列の自己整合である.

テンプレートの問題を1つ置きます.https://www.luogu.org/problemnew/show/P3375
コードは次のとおりです.

 1 #include
 2 #include
 3 using namespace std;
 4 
 5 char s[1000001],t[1000001];
 6 int next[1000001],n,m;
 7 
 8 void getnext(void) {
 9     next[1]=0;
10     int k=0;
11       for (int i=2;i<=m;++i) {
12         while (k>0 && t[i]!=t[k+1]) k=next[k];
13         if (t[i]==t[k+1]) k++;
14         next[i]=k;
15       }
16 }
17 
18 void kmp(void) {
19     int k=0;
20       for (int i=1;i<=n;++i) {
21           while (k>0 && s[i]!=t[k+1]) k=next[k];
22           if (s[i]==t[k+1]) k++;
23           if (k==m) {
24               printf("%d
",i-k+1);
25           }
26       }
27 }
28 
29 int main() {
30     scanf("%s%s",s+1,t+1);
31     n=strlen(s+1); m=strlen(t+1);
32     getnext();
33     kmp();
34       for (int i=1;i<=m;++i) printf("%d ",next[i]);
35     return 0;
36 }

転載先:https://www.cnblogs.com/Gaxc/p/9510556.html

シリアルのパターンマッチングの問題

Pythonコード最適化基盤——判断対象タイプ