文字列マッチングアルゴリズムのKMPまとめ
文字列マッチングには暴力,ハッシュなど多くの方法があり,よく知られているアルゴリズムである−−−KMP−KMP−−KMPがある.
a[1...N]a[1...N]a[1...N]a[1...N]a[1...N]が文字列b[1...M]b[1...M]b[1...M]b[1...M]の文字列であるか否かを線形の時間で判断し、文字列aがbで一致するすべての位置を返すよう要求するアルゴリズムが必要である
思考暴力.
列挙iは、1−>m 1−>m 1−>mからb bが一致する左端点を示し、その後、O(n)O(n)O(n)の判断b[i...i+n−1]b[i...i+n−1]b[i...i+n−1]b[i...i+n−1]がa[1...n]a[1...n]a[1...n]と一致するか否かを示す.
極端なデータの下で走るのが遅い方法を簡単に見つけることができます.例えば、
aの最後の位置に一致するたびに、等しくないことがわかります.時間複雑度O(nm)O(nm)O(nm)O(nm)
もちろんこの問題もハッシュで解決できるが,筆者はここではあまり述べない.
次に不思議なKMP KMPアルゴリズムについてお話しします
KMP KMP KMPアルゴリズムは、モードマッチングアルゴリズムとも呼ばれ、文字列マッチングを効率的かつ正確に処理できるアルゴリズムである
KMPアルゴリズムは基本的に二つの部分に分けられる.
1.まず、A A A配列(パターン列)を自己整合する.
n e x t next next配列を確立し、n e x t[i]next[i]next[i]next[i]は、i i i iで終わる非接頭辞文字列がAの接頭辞と一致できる最大長を表す.
このうち「i i iで終わる非接頭辞文字列」は一般的には非接頭辞の接尾辞であり、例えばaabの非接頭辞の接尾辞は{b},{a b}{b},{ab}{b},{ab}である
n e x t[i]=max{j},j例を挙げます.
A A列を「a b a b a b a b a c」「ababaac」「abababaac」とし、A配列のnext[7]を5とし、導出過程は以下の通りである.
A［i−j＋1…i］＝A［1…j］A［i−j＋1…i］＝A［1…j］A［i］＝A［1…j］A［i−j＋1…i］＝A［1…j］:
A[7...7]={a}A[7...7]={a}A[7...7]={a}はA[1...1]={a}A[1...1]={a}A[1...1]={a}と一致する.A[5...7]={a b a}A[5...7]={aba}A[5...7]={aba}とA[1...3]={a}A[1...3]={a}A[1...3]={a}が一致する.A[3…7]={a b a b a}A[3…7]={aba}A[3…7]={ababa}はA[1..5]={a b a b a}A[1..5]={ababa}A[1.5]={ababa}A[1.5]={ababa}と一致する.
ここでj j jが最も大きいのは3番目の3番目の3番目が5 5である.
n e x t next next配列をより速く計算するにはどうすればいいですか?
n e x t[1...6]next[1...6]next[1...6]next[1...6]が求められているとしてもよく、上記の手順によりn e x t[6]=4 next[6]=4 next[6]=4 next[6]=4
∵ A [ 7 ] = A [ 5 ] , ∴ n e x t [ 7 ] = n e x t [ 6 ] + 1 = 5 ∵A[7]=A[5],∴next[7]=next[6]+1=5 ∵A[7]=A[5],∴next[7]=next[6]+1=5
次にnextを考える[8]
A[8]={a}A[8]={a}A[8]={a}であり、A[6]={b}A[6]={b}A[6]={b}A[6]={b}であることが判明したので、n e x t[8]next[8]next[8]はn e x t[7]+1 next[7]+1 next[7]+1
マッチング長j j jを短くするしかない
以上の結論から,j jが3 3 3と5 5 5に等しいことを知り,A[8]A[8]A[8]A[8]A[8]に拡張しようとした.
しかし、A[8]A[8]A[8]A[8]とA[4]A[4]A[4]とA[2]A[2]A[2]とが一致しないため、最初から一致するしかなく、n e x t[8]=n e x t[1]+1=1 next[8]=next[1]+1=1 next[8]=next[1]+1=1
A[8]!A [ 6 ] A[8]!=A[6] A[8]!=A[6]では、A[4]A[4]A[4]とA[2]A[2]とをマッチングしますか?
n e x t[7]=5 next[7]=5 next[7]=5は、7 7 7から5までの5 5文字がA[1...5]A[1...5]A[1...5]と一致していることを示す.次に探したいのは、5 5 5より前のj j j文字がA[1...j]A[1...j]A[1...j]A[1...j]と一致し、7 7 7より前のj j j文字がA[1...j]A[1...j]A[1...j]と一致することである.このj j jの答えはn e x t[5]next[5]next[5]next[5]であり、実はn e x t[n e x t[7]]next[next[7]]next[next[7]]である.
そこで私たちはこのような方法で次のステップj j j jがどこにジャンプするかを迅速に見つけることができます.
その後,n e x t next nextを前処理するプロセスを実証する.
2.文字列AとBを照合します.
配列f f f,f[i]f[i]f[i]f[i]は、B Bにおけるi i i iを末尾とするサブ列がA A Aのプレフィックスに一致する最大長を示す.
この定義はn e x t next next配列によく似ていることに気づきましたか?はい、彼らは求め方さえほぼ一致しています!
f f fの解のコードを少しあげます:
これが,時間的複雑度O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m
UPD:それから、ペンを動かして図を描くと、n e x t next next配列が木を構成していることがわかります.このようにn e x t next next配列もn e x t nextツリーと呼ばれています.
まずテンプレートの問題です:【テンプレート】KMP文字列マッチング
各f[i]=nf[i]=nf[i]=n f[i]=nの点について、その左端がi−n+1 i−n+1 i−n+1であるので、出力すればよい
コード#コード#
その後は裸題:[USACO 15 FEB]Censoring(Silver)
スタックでメンテナンスを行い、スタック内の接尾辞がモード列に一致する場合は、スタックの接尾辞をスタックから削除します.
マッチングするならKMP KMP KMPで、頭が熱くなるとハッシュを書いてしまい、今はハッシュコードしか残っていません
ハッシュモジュールは1回詰まっていて、31 31 31で37 37を使うことができません.
コード#コード#
速度が速くて一番遅いのは50 m s 50 ms 50 msです
その後この問題はn e x t next next配列に対していくつかの深い理解を行う必要がある:[BOI 2009]Radio Transmission
削除されたものがあるので、このテーマはあまり使いにくいことに気づきました.
最後の一致する接頭辞の長さが列長の1/2/2/2以下である場合、一致する接尾辞の前の部分がループ部分(余分な部分は切り捨て)であることがわかりやすい.
最後の一致する接頭辞の長さが列長の1/2/2/2より大きい場合、一致する接頭辞が接尾辞と完全に等しいため、接頭辞の共通部分を除去する接頭辞は、反復等化によって、この列がこの部分的に繰り返し自己複製されることを証明することができる.
すなわち、接頭辞の非共通部分は接尾辞と等しい長さの接頭辞と等しく、接頭辞の共通部分の接頭辞と等しいだけで、比較を完了する接頭辞と接尾辞は完全に等しく、このように推定される.
だから答えはn−n e x t[n]n−next[n]n−next[n]n−next[n]
コード#コード#
UPD:
ブルーブックのタイトルPeriod
この問題は明らかに二分+ハッシュを使うことができる.
前の問題から,長さnの列の最小サイクルセグメント長はn−n e x t[n]n−next[n]n−next[n]n−next[n]であることが分かったが,この問題でも同様に適用できる.
S[1...i]S[1...i]S[1...i]S[1...i]に長さx xのサイクルがあると仮定すると、x xは必ずi i i i iを除去し、S[1...i−l e n]S[1...i−len]S[1...i−len]S[1...i−len]とS[l e n+1...i]S[len+1...i]S[len+1...i]も等しい(サイクルのため)
前述の結論から,x x xはn−n e x t[n]n−next[n]n−next[n]n−next[n]に等しく,サイクル回数=長さ/サイクルセグメント長であることが分かった.
それで終わりました
Milking Grid
依然として最小サイクルセグメント長に関する問題がある
私たちは削除を恐れない、Radio Transmissionこの問題はすでに私たちにこの結論を教えてくれた.
行ごとに1つの文字として走りながら最小循環節を走り、同理列も1回走ることで循環面積の寸法を求め、彼らを乗じて答えになります
51 nod 1277文字列の最大値
これは素晴らしいテーマで、彼はもう一つのn e x t next next配列の応用を解釈しました.それはn e x t next nextツリーです.
明らかに我々が今解決しなければならない問題は,s u m sum配列表現接頭辞s[1...i]が列に何回現れたかを求め,長さを乗じて答えを算出することである.
これをどうする?
まず、n e x t next nextの意味を本当に理解すれば、簡単に発見できます.
位置j j j jのn e x t[j]=i next[j]=i next[j]=i next[j]=iであれば、彼のS[1.j]S[1.j]S[1.j]S[1..j]S[1..j]にはS[1...i]S[1...i]S[1...i]が必ず現れる.
そこで,s u m[i]=(Σn e x t[j]=i s u m[j])+1 sum[i]=(sumlimits_{next[j]=i}sum[j])+1 sum[i]=(next[j]=iΣsum[j])+1
n e x t[i]<=i next[i]<=i next[i]<=i next[i]<=iを肯定できるので、逆さに列挙して答えを算出します
それから図を描いてn e x t next next配列が木を構成していることを発見しました.n e x t next nextツリーのノードは彼のすべてのサブツリーの接頭辞で、s u m sum配列が格納しているのは実は彼のサブツリーの大きさです.
NOI 2014動物園
暴力統計n u m num num配列はずっと前へ走って、きっとT
どのように最適化しますか?
この問題の鍵は前後の2つの文字列(接頭辞と接尾辞)が重なることができないことであることを発見した.
では、この条件を無視して交差するa n s ans配列を求めると、n u m num配列はn u m[i]=a n s[j]num[i]=ans[j]num[i]=ans[j]num[i]=ans[j]=ans[j](j j j jはi i i i iの半分未満の数であり、n e x t next next上でジャンプすることが明らかになる.
さて本題のポイントはa n s ans ans配列を求めることにあるが,明らかなのはK M P KMP KMPを求めるついでに発売すればよいことである
そしてn u m num配列を使って投げてしまうので、求める必要はありません!!
ああ、NOIの問題はこのように切られたの?いい感じですね.
それから私はまた1つの問題をしなければなりません:GT試験、llsを聞いて矩乗+KMPだと言います
この問題は無理に宿題にしよう
一.問題の導入
a[1...N]a[1...N]a[1...N]a[1...N]a[1...N]が文字列b[1...M]b[1...M]b[1...M]b[1...M]の文字列であるか否かを線形の時間で判断し、文字列aがbで一致するすべての位置を返すよう要求するアルゴリズムが必要である
思考暴力.
列挙iは、1−>m 1−>m 1−>mからb bが一致する左端点を示し、その後、O(n)O(n)O(n)の判断b[i...i+n−1]b[i...i+n−1]b[i...i+n−1]b[i...i+n−1]がa[1...n]a[1...n]a[1...n]と一致するか否かを示す.
極端なデータの下で走るのが遅い方法を簡単に見つけることができます.例えば、
aaaaaaaaaaaaaaaaaab
aaaaab
aの最後の位置に一致するたびに、等しくないことがわかります.時間複雑度O(nm)O(nm)O(nm)O(nm)
もちろんこの問題もハッシュで解決できるが,筆者はここではあまり述べない.
次に不思議なKMP KMPアルゴリズムについてお話しします
二.アルゴリズムの概要
KMP KMP KMPアルゴリズムは、モードマッチングアルゴリズムとも呼ばれ、文字列マッチングを効率的かつ正確に処理できるアルゴリズムである
KMPアルゴリズムは基本的に二つの部分に分けられる.
1.まず、A A A配列(パターン列)を自己整合する.
n e x t next next配列を確立し、n e x t[i]next[i]next[i]next[i]は、i i i iで終わる非接頭辞文字列がAの接頭辞と一致できる最大長を表す.
このうち「i i iで終わる非接頭辞文字列」は一般的には非接頭辞の接尾辞であり、例えばaabの非接頭辞の接尾辞は{b},{a b}{b},{ab}{b},{ab}である
n e x t[i]=max{j},j例を挙げます.
A A列を「a b a b a b a b a c」「ababaac」「abababaac」とし、A配列のnext[7]を5とし、導出過程は以下の通りである.
A［i−j＋1…i］＝A［1…j］A［i−j＋1…i］＝A［1…j］A［i］＝A［1…j］A［i−j＋1…i］＝A［1…j］:
A[7...7]={a}A[7...7]={a}A[7...7]={a}はA[1...1]={a}A[1...1]={a}A[1...1]={a}と一致する.A[5...7]={a b a}A[5...7]={aba}A[5...7]={aba}とA[1...3]={a}A[1...3]={a}A[1...3]={a}が一致する.A[3…7]={a b a b a}A[3…7]={aba}A[3…7]={ababa}はA[1..5]={a b a b a}A[1..5]={ababa}A[1.5]={ababa}A[1.5]={ababa}と一致する.
ここでj j jが最も大きいのは3番目の3番目の3番目が5 5である.
n e x t next next配列をより速く計算するにはどうすればいいですか?
n e x t[1...6]next[1...6]next[1...6]next[1...6]が求められているとしてもよく、上記の手順によりn e x t[6]=4 next[6]=4 next[6]=4 next[6]=4
∵ A [ 7 ] = A [ 5 ] , ∴ n e x t [ 7 ] = n e x t [ 6 ] + 1 = 5 ∵A[7]=A[5],∴next[7]=next[6]+1=5 ∵A[7]=A[5],∴next[7]=next[6]+1=5
次にnextを考える[8]
A[8]={a}A[8]={a}A[8]={a}であり、A[6]={b}A[6]={b}A[6]={b}A[6]={b}であることが判明したので、n e x t[8]next[8]next[8]はn e x t[7]+1 next[7]+1 next[7]+1
マッチング長j j jを短くするしかない
以上の結論から,j jが3 3 3と5 5 5に等しいことを知り,A[8]A[8]A[8]A[8]A[8]に拡張しようとした.
しかし、A[8]A[8]A[8]A[8]とA[4]A[4]A[4]とA[2]A[2]A[2]とが一致しないため、最初から一致するしかなく、n e x t[8]=n e x t[1]+1=1 next[8]=next[1]+1=1 next[8]=next[1]+1=1
A[8]!A [ 6 ] A[8]!=A[6] A[8]!=A[6]では、A[4]A[4]A[4]とA[2]A[2]とをマッチングしますか?
n e x t[7]=5 next[7]=5 next[7]=5は、7 7 7から5までの5 5文字がA[1...5]A[1...5]A[1...5]と一致していることを示す.次に探したいのは、5 5 5より前のj j j文字がA[1...j]A[1...j]A[1...j]A[1...j]と一致し、7 7 7より前のj j j文字がA[1...j]A[1...j]A[1...j]と一致することである.このj j jの答えはn e x t[5]next[5]next[5]next[5]であり、実はn e x t[n e x t[7]]next[next[7]]next[next[7]]である.
そこで私たちはこのような方法で次のステップj j j jがどこにジャンプするかを迅速に見つけることができます.
その後,n e x t next nextを前処理するプロセスを実証する.
next[1] = 0 ; // next[1]=0
for (int i = 2, j = 0; i <= n; i++) { // next[i] next[1...i-1]
while (j && a[i] != a[j + 1]) j = next[j] ; // j ， ， next[j] ； ， next[i]=0
if (a[i] == a[j + 1]) j++ ; // ， j 1。
next[i] = j ; // next[i] j
}
2.文字列AとBを照合します.
配列f f f,f[i]f[i]f[i]f[i]は、B Bにおけるi i i iを末尾とするサブ列がA A Aのプレフィックスに一致する最大長を示す.
この定義はn e x t next next配列によく似ていることに気づきましたか?はい、彼らは求め方さえほぼ一致しています!
f f fの解のコードを少しあげます:
for (int i = 1, j = 0; i <= m; i++) {
while (j && (j == n || b[i] != a[j + 1])) j = next[j] ;
if (b[i] == a[j + 1]) j++ ;
f[i] = j ;
if (f[i] == n) ans++ ; // n， ， ++
}
これが,時間的複雑度O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m)O(n＋m
UPD:それから、ペンを動かして図を描くと、n e x t next next配列が木を構成していることがわかります.このようにn e x t next next配列もn e x t nextツリーと呼ばれています.
三.例題選講
まずテンプレートの問題です:【テンプレート】KMP文字列マッチング
各f[i]=nf[i]=nf[i]=n f[i]=nの点について、その左端がi−n+1 i−n+1 i−n+1であるので、出力すればよい
コード#コード#
その後は裸題:[USACO 15 FEB]Censoring(Silver)
スタックでメンテナンスを行い、スタック内の接尾辞がモード列に一致する場合は、スタックの接尾辞をスタックから削除します.
マッチングするならKMP KMP KMPで、頭が熱くなるとハッシュを書いてしまい、今はハッシュコードしか残っていません
ハッシュモジュールは1回詰まっていて、31 31 31で37 37を使うことができません.
コード#コード#
速度が速くて一番遅いのは50 m s 50 ms 50 msです
その後この問題はn e x t next next配列に対していくつかの深い理解を行う必要がある:[BOI 2009]Radio Transmission
削除されたものがあるので、このテーマはあまり使いにくいことに気づきました.
最後の一致する接頭辞の長さが列長の1/2/2/2以下である場合、一致する接尾辞の前の部分がループ部分(余分な部分は切り捨て)であることがわかりやすい.
最後の一致する接頭辞の長さが列長の1/2/2/2より大きい場合、一致する接頭辞が接尾辞と完全に等しいため、接頭辞の共通部分を除去する接頭辞は、反復等化によって、この列がこの部分的に繰り返し自己複製されることを証明することができる.
すなわち、接頭辞の非共通部分は接尾辞と等しい長さの接頭辞と等しく、接頭辞の共通部分の接頭辞と等しいだけで、比較を完了する接頭辞と接尾辞は完全に等しく、このように推定される.
だから答えはn−n e x t[n]n−next[n]n−next[n]n−next[n]
コード#コード#
UPD:
ブルーブックのタイトルPeriod
この問題は明らかに二分+ハッシュを使うことができる.
前の問題から,長さnの列の最小サイクルセグメント長はn−n e x t[n]n−next[n]n−next[n]n−next[n]であることが分かったが,この問題でも同様に適用できる.
S[1...i]S[1...i]S[1...i]S[1...i]に長さx xのサイクルがあると仮定すると、x xは必ずi i i i iを除去し、S[1...i−l e n]S[1...i−len]S[1...i−len]S[1...i−len]とS[l e n+1...i]S[len+1...i]S[len+1...i]も等しい(サイクルのため)
前述の結論から,x x xはn−n e x t[n]n−next[n]n−next[n]n−next[n]に等しく,サイクル回数=長さ/サイクルセグメント長であることが分かった.
それで終わりました
Milking Grid
依然として最小サイクルセグメント長に関する問題がある
私たちは削除を恐れない、Radio Transmissionこの問題はすでに私たちにこの結論を教えてくれた.
行ごとに1つの文字として走りながら最小循環節を走り、同理列も1回走ることで循環面積の寸法を求め、彼らを乗じて答えになります
51 nod 1277文字列の最大値
これは素晴らしいテーマで、彼はもう一つのn e x t next next配列の応用を解釈しました.それはn e x t next nextツリーです.
明らかに我々が今解決しなければならない問題は,s u m sum配列表現接頭辞s[1...i]が列に何回現れたかを求め,長さを乗じて答えを算出することである.
これをどうする?
まず、n e x t next nextの意味を本当に理解すれば、簡単に発見できます.
位置j j j jのn e x t[j]=i next[j]=i next[j]=i next[j]=iであれば、彼のS[1.j]S[1.j]S[1.j]S[1..j]S[1..j]にはS[1...i]S[1...i]S[1...i]が必ず現れる.
そこで,s u m[i]=(Σn e x t[j]=i s u m[j])+1 sum[i]=(sumlimits_{next[j]=i}sum[j])+1 sum[i]=(next[j]=iΣsum[j])+1
n e x t[i]<=i next[i]<=i next[i]<=i next[i]<=iを肯定できるので、逆さに列挙して答えを算出します
それから図を描いてn e x t next next配列が木を構成していることを発見しました.n e x t next nextツリーのノードは彼のすべてのサブツリーの接頭辞で、s u m sum配列が格納しているのは実は彼のサブツリーの大きさです.
NOI 2014動物園
暴力統計n u m num num配列はずっと前へ走って、きっとT
どのように最適化しますか?
この問題の鍵は前後の2つの文字列(接頭辞と接尾辞)が重なることができないことであることを発見した.
では、この条件を無視して交差するa n s ans配列を求めると、n u m num配列はn u m[i]=a n s[j]num[i]=ans[j]num[i]=ans[j]num[i]=ans[j]=ans[j](j j j jはi i i i iの半分未満の数であり、n e x t next next上でジャンプすることが明らかになる.
さて本題のポイントはa n s ans ans配列を求めることにあるが,明らかなのはK M P KMP KMPを求めるついでに発売すればよいことである
そしてn u m num配列を使って投げてしまうので、求める必要はありません!!
ああ、NOIの問題はこのように切られたの?いい感じですね.
それから私はまた1つの問題をしなければなりません:GT試験、llsを聞いて矩乗+KMPだと言います
この問題は無理に宿題にしよう