カテゴリー:
探索アルゴリズム
閲覧数:369 配信日:2018-08-06 11:03
具体例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法の違い
文字列の頭良い感じの線形アルゴリズムたち