border とは？

border とは？

ある文字列の prefix と suffix が一致している場合の、一致している prefix と suffix
・ある文字列の prefix と suffix が一致している場合、一致している prefix と suffix をその文字列の border と呼ぶ
・但し、prefix と suffix は重複する部分があってもよいが一致していてはいけない
・border が空文字でも OK
・空文字には border が存在しない
・最も幅広い border を tagged border と呼ぶ

tagged borderの具体例

ababaa
・a


Knuth-Morris-Pratt algorithm

文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
string - Knuth–Morris–Pratt algorithm: border array - Stack Overflow
Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search) - YouTube
algorithm - Finding the longest border of a string - Stack Overflow
Knuth-Morris-Pratt algorithm - コードの恵み
Knuth-Morris-Pratt algorithm

・MP法とKMP法の違い
Knuth-Morris-Pratt algorithm
http://winnie.kuis.kyoto-u.ac.jp/members/okuno/Lecture/02/DataStructure/ds-02-13.pdf