カテゴリー:
探索アルゴリズム
閲覧数:315 配信日:2018-07-06 09:28
検索文字列パターン
・ここでは変数Sとして定義
const S = 'なるべくなる';
border
「単語の2文字目で不一致となった場合のバックトラックする文字数」で構成された配列
・ここでは配列Aとして定義
const A = [];
コード
const S = 'なるべくなる';
const A = [];
A[0] = -1;
let j = -1;
for (let i = 0; i < S.length; i++) {
while (j >= 0 && S[i] != S[j]) j = A[j];
j++;
A[i+1] = j;
}
console.log(A); //(7) [-1, 0, 0, 0, 0, 1, 2]
i0,j-1,A[-1]
| な | る | べ | く | な | る |
|---|
・+1して、j=0
・A[1]=0
i1,j0,A[-1,0]
| な | る | べ | く | な | る |
|---|
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[2]=0
※「な」よリ前と「る」よリ前を比較して、「な」と「る」が一致していないので「0」
i2,j0,A[-1,0,0]
| な | る | べ | く | な | る |
|---|
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[3]=0
※「な」よリ前と「べ」よリ前を比較して、「な」と「べ」が一致していないので「0」
i3,j0,A[-1,0,0,0]
| な | る | べ | く | な | る |
|---|
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[4]=0
※「な」よリ前と「く」よリ前を比較して、「な」と「く」が一致していないので「0」
i4,j0,A[-1,0,0,0,0]
| な | る | べ | く | な | る |
|---|
・+1して、j=1
・A[5]=1
※「な」よリ前と「な」よリ前を比較して、「な」と「な」が一致しているので「1」
i5,j1,A[-1,0,0,0,0,1]
| な | る | べ | く | な | る |
|---|
・+1して、j=2
・A[6]=2
※「る」よリ前と「る」よリ前を比較して、「なる」と「なる」が一致しているので「2」
i6,j2,A[-1,0,0,0,0,1,2]
Morris-Pratt algorithm
Crochemore-Perrin アルゴリズム
文字列の頭良い感じの線形アルゴリズムたち
https://www.cs.helsinki.fi/u/tpkarkka/teach/15-16/SPA/lecture04.pdf
https://www.cs.helsinki.fi/u/hahonen/irm07/lectures/irm07_8.pdf
・終了後 → KMP法