例1.'aabaabaaa' → 配列(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]

日本語で考える

文字列
・ 'aabaabaaa'

求める結果
・配列(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]

インデックス0
・-1
・配列(1) [-1]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1

インデックス1まで … a
・比較しようがないため0
・配列(2) [-1,0]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0

インデックス2まで … aa
・borderはa … 数1
・配列(3) [-1,0,1]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0
2	'aa'	'a'	1

インデックス3まで … aab
・borderはなし … 数0
・配列(4) [-1,0,1,0]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0
2	'aa'	'a'	1
3	'aab'	''	0

インデックス4まで … aaba
・borderはa … 数1
・配列(5) [-1,0,1,0,1]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0
2	'aa'	'a'	1
3	'aab'	''	0
4	'aaba'	'a'	1

インデックス5まで … aabaa
・borderはaa … 数2
・配列(6) [-1,0,1,0,1,2]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0
2	'aa'	'a'	1
3	'aab'	''	0
4	'aaba'	'a'	1
5	'aabaa'	'aa'	2

インデックス6まで … aabaab
・aabとaabが一致しているため3
・配列(7) [-1,0,1,0,1,2,3]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0
2	'aa'	'a'	1
3	'aab'	''	0
4	'aaba'	'a'	1
5	'aabaa'	'aa'	2
6	'aabaab'	'aab'	3

インデックス7まで … aabaaba
・aabaとaabaが一致しているため4
・配列(8) [-1,0,1,0,1,2,3,4]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0
2	'aa'	'a'	1
3	'aab'	''	0
4	'aaba'	'a'	1
5	'aabaa'	'aa'	2
6	'aabaab'	'aab'	3
7	'aabaaba'	'aaba'	4

インデックス8まで … aabaabaa
・aabaaとaabaaが一致しているため5
・配列(9) [-1,0,1,0,1,2,3,4,5]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0
2	'aa'	'a'	1
3	'aab'	''	0
4	'aaba'	'a'	1
5	'aabaa'	'aa'	2
6	'aabaab'	'aab'	3
7	'aabaaba'	'aaba'	4
8	'aabaabaa'	'aabaa'	5

インデックス9まで … aabaabaaa
・aaとaaが一致しているため2
・配列(10) [-1,0,1,0,1,2,3,4,5,2]

インデックス	文字列	border	数
0	存在しない	特別なケース	文字内容に関わらず常に固定値-1
1	'a'	''	0
2	'aa'	'a'	1
3	'aab'	''	0
4	'aaba'	'a'	1
5	'aabaa'	'aa'	2
6	'aabaab'	'aab'	3
7	'aabaaba'	'aaba'	4
8	'aabaabaa'	'aabaa'	5
9	'aabaabaaa'	'aa'	2

コードステップ

ECMASCript2015

const S = 'aabaabaaa';

const A = [];

A[0] = -1; //特別なケース。文字内容に関わらず常に固定値-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); //(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]

JavaScript

var S = 'abbabba';

var A = [];

A[0] = -1; //特別なケース。文字内容に関わらず常に固定値-1

var j = -1;

for (var i = 0; i < S.length; i++) { // i < 7

  while (j >= 0 && S[i] != S[j]) j = A[j];

  j++;

  A[i+1] = j;

  console.log(i); //0 1 2 3 4 5 6

  console.log(j); //0 0 0 1 2 3 4

}

console.log(A); //(8) [-1, 0, 0, 0, 1, 2, 3, 4]

i0,j-1,A[-1]

a	b	b	a	b	b	a

・false(j >= 0 を満たさない)なので、while文に入らず通過
・+1して、j0
・A[1]=0

i1,j0,A[-1,0]

a	b	b	a	b	b	a

・true(b≠a)なので、A[0]よりj=-1
・false(j >= 0 を満たさない)なので、while文のループ終了
・+1して、j0
・A[2]=0
※「a」以前と「b」以前を比較して、「a」と「b」が一致していないので「0」

i2,j0,A[-1,0,0]

a	b	b	a	b	b	a

・true(b≠a)なので、A[0]よりj=-1
・false(j >= 0 を満たさない)なので、while文のループ終了
・+1して、j0
・A[3]=0
※「a」以前と「b」以前を比較して、「a」と「b」が一致していないので「0」

i3,j0,A[-1,0,0,0]

a	b	b	a	b	b	a

・false(a == a)なので、while文に入らず通過
・+1して、j1
・A[4]=1
※「a」以前と「a」以前を比較して、「a」と「a」が一致しているので「1」

i4,j1,A[-1,0,0,0,1]

a	b	b	a	b	b	a

・false(b == b)なので、while文に入らず通過
・+1して、j2
・A[5]=2
※「b」以前と「b」以前を比較して、「ab」と「ab」が一致しているので「2」

i5,j2,A[-1,0,0,0,1,2]

a	b	b	a	b	b	a

・false(b == b)なので、while文に入らず通過
・+1して、j3
・A[6]=3
※「b」以前と「b」以前を比較して、「abb」と「abb」が一致しているので「3」

i6,j3,A[-1,0,0,0,1,2,3]

a	b	b	a	b	b	a

・false(a == a)なので、while文に入らず通過
・+1して、j4
・A[7]=4
※「a」以前と「a」以前を比較して、「abba」と「abba」が一致しているので「4」

i7,j4,A[-1,0,0,0,1,2,3,4]

検索文字列パターン	_	a	b	b	a	b	b	a
border	-1	0	0	0	1	2	3	4
0	_	ji	_	_	_	_	_	_
1	_	j	i	_	_	_	_	_
2	_	j	_	i	_	_	_	_
3	_	_	j	_	i	_	_	_
4	_	_	_	j	_	i	_	_
5	_	_	_	_	j	_	i	_
6	_	_	_	_	_	j	_	i