border

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

borderとは?

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

具体例

 閲覧数:198 投稿日: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 Subversion 50
2 YouTube 46
3 Markdown 43
4 WebLogic 43
5 attribute 40
6 cron 40
7 WebM 40
8 Hibernate 40
9 PowerShell 38
10 Chromecast 38
11 Plone 36
12 Apache Solr 35
13 mod_deflate 35
14 Flash Video 35
15 バッファ【buffer】 33
16 Facebookピクセル 33
17 MeCab 33
18 Webサーバ 33
19 activeCollab 33
20 Headless Browsers 33
2022/7/01 5:22 更新
週間人気ページランキング / 6-24 → 6-30
順位 ページタイトル抜粋 アクセス数
1 Flash Video | コンテナフォーマット | プログラミング用語 306
2 curl | HTTPクライアント(ネットワーク) | プログラミング用語 286
3 ルーター | ネットワーク | プログラミング用語 281
3 ユースケース | 開発 | プログラミング用語 281
4 ベクトル | 数学 | プログラミング用語 236
5 デーモン | Linux | プログラミング用語 227
6 正規表現 | プログラミング | プログラミング用語 194
7 YouTube | API | プログラミング用語 171
8 チェックアウト | バージョン管理システム(開発) | プログラミング用語 117
9 分かち書き | 形態素解析 | プログラミング用語 63
10 Linux | プログラミング用語 57
11 リバースエンジニアリング | 開発 | プログラミング用語 54
12 ネットワークアドレス | ネットワーク | プログラミング用語 50
13 PowerShell | スクリプト | プログラミング用語 44
14 クローラ | 検索エンジン | プログラミング用語 31
14 可搬性 | プログラミング | プログラミング用語 31
15 Subversion | バージョン管理システム(開発) | プログラミング用語 27
16 アンチパターン | プログラミング | プログラミング用語 11
17 プログラミング用語 9
18 deflate | ネットワーク | プログラミング用語 8
2022/7/1 1:01 更新