borderとは？
状態:-
閲覧数:1,491
投稿日:2018-08-06
更新日:2018-08-10
表記
日本語
・境界
文字列 s に対し， s の接頭辞でもあり接尾辞でもある文字列
接尾辞 接頭辞の最大長
・文字列sの接尾辞（ただしs自身は除く）の中でsの接頭辞でもあるものの最大長
・文字列Sの部分文字列であって、Sの接頭辞かつ接尾辞であるような文字列のこと
・ある文字列の 接頭辞 と suffix が一致している場合、一致している prefix と suffix をその文字列の border と呼ぶ
・ただし prefix と suffix は重複する部分があってもよいが一致していてはいけない
・border が空文字でも OK
・空文字には border が存在しない
・最も幅広い border を tagged border と呼ぶ
具体例
具体例1
| 文字列 | border | 備考 |
|---|---|---|
| "ababaa" | "a" | - |
| "ababa" | "aba" | prefix と suffix で a を共有している |
| "abab" | "ab" | - |
| "aba" | "a" | - |
| "ab" | ”” | border が空文字の場合もある |
| "a" | "" | - |
| "" | null | 空文字に border は存在しない |
具体例2
| 検索文字列パターン | a | a | b | a | a | b | a | a | a |
|---|---|---|---|---|---|---|---|---|---|
| borderの数 | 0 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 2 |
| 文字列 | border | 数 |
|---|---|---|
| "a" | "" | 0 |
| "aa" | "a" | 1 |
| "aab" | "" | 0 |
| "aaba" | "a" | 1 |
| "aabaa" | ”aa” | 2 |
| "aabaab" | "aab" | 3 |
| "aabaaba" | "aaba" | 4 |
| "aabaabaa" | "aabaa" | 5 |
| "aabaabaaa" | "aa" | 2 |
具体例3
| 検索文字列パターン | な | る | べ | く | な | る |
|---|---|---|---|---|---|---|
| borderの数 | 0 | 0 | 0 | 0 | 1 | 2 |
| 文字列 | border | 数 |
|---|---|---|
| "な" | "" | 0 |
| "なる" | "" | 0 |
| "なるべ" | "" | 0 |
| "なるべく" | "" | 0 |
| "なるべくな" | ”な” | 1 |
| "なるべくなる" | "なる" | 2 |
境界 (border)
接尾辞 接頭辞の最大長
MP法とKMP法の違い
文字列の頭良い感じの線形アルゴリズムたち