Border
Basic Concept
Given a string \(w\), a border of \(w\) is a string that both a prefix and a suffix of \(w\). \(w\) and the empty string \(\varepsilon\) is border of \(w\).
The longest non-trivial border of \(w\) is denoted by \(Border(w)\).
Note
For example, \(Border(abaababa) = aba\).
Border has a close relation with Period.
Algorithms
Consider a problem to find the border array of given string.
Given a string \(w\), the border array of \(w\) is an array \(border\) such that \(border[i] = Border(w[:i])\).
Note
The border array of string abaababa
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|---|---|---|---|---|---|---|---|---|---|
character |
a |
b |
a |
a |
b |
a |
b |
a |
|
border |
-1 |
0 |
0 |
1 |
1 |
2 |
3 |
2 |
3 |
The border array is used in Knuth-Morris-Pratt法．
Naive algorithm
Linear time algorithm
compute_border1
/Scripts/Python/compute_border1.py
compute_border2
/Scripts/Python/compute_border2.py