border

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

borderとは?

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

具体例

 閲覧数:251 投稿日: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法の違い
文字列の頭良い感じの線形アルゴリズムたち 

Twitter検索結果。「border」に関する最新ツイート

ネモ|常行丼@後戸満天祭 空-28 @Nemo_Border
そうらしい 2023/02/06 02:59
ボーダー @border_bot
貴人【死線】 @Border_of_none

Morris-Pratt algorithm border

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



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