border

アルゴリズム探索アルゴリズム

borderとは?

 状態:-  閲覧数:1,445  投稿日: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 と呼ぶ

具体例

 閲覧数:344 投稿日:2018-08-06 更新日:2018-09-02 

具体例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法の違い
文字列の頭良い感じの線形アルゴリズムたち 


Morris-Pratt algorithm border

コメント投稿(ログインが必要)



類似度ページランキング
順位 ページタイトル抜粋
1 border 83
2 Subversion 50
3 YouTube 46
4 WebLogic 43
5 Markdown 43
6 Hibernate 40
7 attribute 40
8 cron 40
9 WebM 40
10 Chromecast 38
11 PowerShell 38
12 Plone 36
13 Apache Solr 35
14 mod_deflate 35
15 Flash Video 35
16 stable build 33
17 latest build 33
18 MeCab 33
19 activeCollab 33
20 バッファ【buffer】 33
2024/7/23 6:14 更新