カテゴリー:
探索アルゴリズム
閲覧数:330 配信日:2018-06-12 08:02
例2
コード
var S = 'aabaabaaa';
var A = [];
A[0] = -1;
var j = -1;
for (var i = 0; i < S.length; i++) {
console.log(j); //-1 0 1 0 1 2 3 4 5
while (j >= 0 && S[i] != S[j]) j = A[j]; //trueの間はfalseになるまで繰り返す
console.log(j); //-1 0 -1 0 1 2 3 4 1
j++;
A[i+1] = j;
//console.log(i); //0 1 2 3 4 5 6 7 8
//console.log(j); //0 1 0 1 2 3 4 5 2
}
console.log(A); //(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]
i0,j-1,A[-1]
| a | a | b | a | a | b | a | a | a |
|---|
・+1して、j=0
・A[1]=0
i1,j0,A[-1,0]
| a | a | b | a | a | b | a | a | a |
|---|
・+1して、j=1
・A[2]=1
※「a」よリ前と「a」よリ前を比較して、「a」と「a」が一致しているので「1」
i2,j1,A[-1,0,1]
| a | a | b | a | a | b | a | a | a |
|---|
・s[2]!=s[0]はtrue(b≠a)なので、A[0]よりj=-1
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[3]=0
※「a」よリ前と「b」よリ前を比較して、「a」と「b」が一致していないので「0」
i3,j0,A[-1,0,1,0]
| a | a | b | a | a | b | a | a | a |
|---|
・+1して、j1
・A[4]=1
※「a」よリ前と「a」よリ前を比較して、「a」と「a」が一致しているので「1」
i4,j1,A[-1,0,1,0,1]
| a | a | b | a | a | b | a | a | a |
|---|
・+1して、j=2
・A[5]=2
※「a」よリ前と「a」よリ前を比較して、「aa」と「aa」が一致しているので「2」
i5,j2,A[-1,0,1,0,1,2]
| a | a | b | a | a | b | a | a | a |
|---|
・+1して、j3
・A[6]=3
※「b」よリ前と「b」よリ前を比較して、「aab」と「aab」が一致しているので「3」
i6,j3,A[-1,0,1,0,1,2,3]
| a | a | b | a | a | b | a | a | a |
|---|
・+1して、j=4
・A[7]=4
※「a」よリ前と「a」よリ前を比較して、「aaba」と「aaba」が一致しているので「4」
i7,j4,A[-1,0,1,0,1,2,3,4]
| a | a | b | a | a | b | a | a | a |
|---|
・+1して、j=5
・A[8]=5
※「a」よリ前と「a」よリ前を比較して、「aabaa」と「aabaa」が一致しているので「5」
i8,j5,A[-1,0,1,0,1,2,3,4,5]
| a | a | b | a | a | b | a | a | a |
|---|
・s[8]!=s[2]はtrue(a≠b)なので、A[2]よりj=1
・s[8]!=s[1]はfalse(a==a)なので、while文のループ終了
・+1して、j=2
・A[9]=2
i9,j2,A[-1,0,1,0,1,2,3,4,5,2]
| 検索文字列パターン | _ | a | a | b | a | a | b | a | a | a |
|---|---|---|---|---|---|---|---|---|---|---|
| border | -1 | 0 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 2 |
| 0 | _ | ji | _ | _ | _ | _ | _ | _ | _ | _ |
| 1 | _ | _ | ji | _ | _ | _ | _ | _ | _ | _ |
| 2 | _ | j | _ | i | _ | _ | _ | _ | _ | _ |
| 3 | _ | _ | j | _ | i | _ | _ | _ | _ | _ |
| 4 | _ | _ | _ | j | _ | i | _ | _ | _ | _ |
| 5 | _ | _ | _ | _ | j | _ | i | _ | _ | _ |
| 6 | _ | _ | _ | _ | _ | j | _ | i | _ | _ |
| 7 | _ | _ | _ | _ | _ | _ | j | _ | i | _ |
| 8 | _ | _ | j | _ | _ | _ | _ | _ | _ | i |