境界 (border)¶
基本概念¶
文字列 \(w\) に対し, \(w\) の接頭辞でもあり接尾辞でもある文字列を \(w\) の 境界 (border) という. \(w\) 自身と,空語 \(\varepsilon\) は常に \(w\) の境界である.
\(w\) の自明でない(つまり \(w\) 自身ではない)最長の境界を \(Border(w)\) と表す.
注釈
例えば, \(Border(abaababa) = aba\) である.
境界は, 周期 (period) と表裏の関係にある.
アルゴリズム¶
入力として与えられた文字列の境界配列 (border array)を求める問題
文字列 \(w\) に対し, \(border[i] = Border(w[:i])\) で定義される配列 \(border\) を考える.
注釈
文字列 abaababa に対する境界配列
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
文字 | a | b | a | a | b | a | b | a | |
border | -1 | 0 | 0 | 1 | 1 | 2 | 3 | 2 | 3 |
この境界配列は, Knuth-Morris-Pratt法 の肝になっている.
def border():
inp = raw_input()
bordArray = [-1]
bord = 0
for i in range(len(inp)):
pref = inp[:i+1]
for j in range(len(pref)):
if pref[-len(pref[:j+1]):] == pref[:j+1] and len(pref[:j+1]) != len(pref):
bord = max(bord,len(pref[:j+1]))
print("bord =",bord)
bordArray.append(bord)
bord = 0
return bordArray
- 線形時間の方法
- compute_border1
/Scripts/Python/compute_border1.py
def compute_border1():
pat = raw_input()
"""-1で初期化"""
m = len(pat)
Bord = [-1]*(m+1)
pat = " " + pat
i,j = 1,0
while i < m + 1:
if Bord[i+j] == -1:
Bord[i+j] = j;
while i + j < m and pat[j+1] == pat[i+j+1]:
j += 1
if Bord[i+j] == -1:
Bord[i+j] = j;
i = i + j - Bord[j]
j = max(0,Bord[j])
return Bord
- compute_border2
/Scripts/Python/compute_border2.py
def compute_border2():
pat = raw_input()
t = -1
Bord = [-1]
#"""-1で初期化"""
#for i in range(len(pat)):
# Bord.append(-1)
"""パターンの長さm"""
m = len(pat)
"""patを[1...m]に"""
pat = " " + pat
for j in range(m):
while t >= 0 and pat[t+1] != pat[j+1]:
t = Bord[t];
t = t + 1
#Bord[j+1] = t
Bord.append(t)
return Bord