Morris-Pratt algorithm

前提

検索文字列パターン

border
・「単語の2文字目で不一致となった場合のバックトラックする文字数」で構成された配列
※配列名は任意だが、慣用的にborderを使用することが多い

比較再開テーブルを作成

インデックス	0	1	2	3	4	5
検索文字列パターン	な	る	べ	く	な	る

比較再開テーブル0

border[0]を-1 とする
・パターン最初の部分での不一致は特別なケース（バックトラッキングの可能性はない）ので、 border[0] = -1を設定
※文字内容に関わらず常に固定値-1

インデックス	0	1	2	3	4	5
検索文字列パターン	な	る	べ	く	な	る
border	-1	.	.	.	.	.

比較再開テーブル1

border[1]を0 とする
・単語の2文字目で不一致となった場合のバックトラックする文字数であるが、(仮に一致した状態であったとしても)1文字しか一致していない状態ではバックトラックできないため
※文字内容に関わらず常に固定値0

計算式に無理やり当てはめてみる
・検索文字列パターン[0] から 検索文字列パターン[1-1] までの文字列について、検索文字列パターン[1-1] で終わる文字列と 検索文字列パターン[0] から始まる文字列が一致するかどうかを調べる
・「な」から「な」までの文字列について、「な」 と 「な」 が一致するかどうかを調べる

インデックス	0	1	2	3	4	5
検索文字列パターン	な	る	べ	く	な	る
border	-1	0	.	.	.	.

比較再開テーブル2

border[2]を0 とする
・検索文字列パターン[0] から 検索文字列パターン[2-1] までの文字列について、検索文字列パターン[2-1] で終わる文字列と 検索文字列パターン[0] から始まる文字列が一致するかどうかを調べる
・「な」から「る」までの文字列について、「る」 と 「な」 が一致するかどうかを調べる
・一致していないので「0」

インデックス	0	1	2	3	4	5
検索文字列パターン	な	る	べ	く	な	る
border	-1	0	0	.	.	.

日本語で考える

文字列
・ '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

例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

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

i1,j0,A[-1,0]

a	a	b	a	a	b	a	a	a

・false(a == a)なので、while文に入らず通過
・+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

・true(b≠a)なので、A[1]よりj=0
・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

・false(a == a)なので、while文に入らず通過
・+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

・false(a == a)なので、while文に入らず通過
・+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

・false(b == b)なので、while文に入らず通過
・+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

・false(a == a)なので、while文に入らず通過
・+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

・false(a == a)なので、while文に入らず通過
・+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

・true(a != b)なので、A[5]よりj=2
・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

検索文字列パターン

・ここでは変数Sとして定義

border

「単語の2文字目で不一致となった場合のバックトラックする文字数」で構成された配列
・ここでは配列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]

な	る	べ	く	な	る

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

i1,j0,A[-1,0]

な	る	べ	く	な	る

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

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

な	る	べ	く	な	る

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

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

な	る	べ	く	な	る

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

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

な	る	べ	く	な	る

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

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

な	る	べ	く	な	る

・false(る == る)なので、while文に入らず通過
・+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法