具体例

「プログラミング」及び「開発」関連用語集

カテゴリー: 探索アルゴリズム  閲覧数:321 配信日: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
Knuth-Morris-Pratt algorithm
境界 (border) 
接尾辞 接頭辞の最大長
MP法とKMP法の違い
文字列の頭良い感じの線形アルゴリズムたち