border とは?

カテゴリー: プログラミング  閲覧数:474 配信日:2018-03-16 10:36


border とは?


ある文字列の prefix と suffix が一致している場合の、一致している prefix と suffix
・ある文字列の prefix と suffix が一致している場合、一致している prefix と suffix をその文字列の border と呼ぶ
・但し、prefix と suffix は重複する部分があってもよいが一致していてはいけない
・border が空文字でも OK
・空文字には border が存在しない
・最も幅広い border を tagged border と呼ぶ

tagged borderの具体例


ababaa
・a


Knuth-Morris-Pratt algorithm

文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
string - Knuth–Morris–Pratt algorithm: border array - Stack Overflow
Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search) - YouTube
algorithm - Finding the longest border of a string - Stack Overflow
Knuth-Morris-Pratt algorithm - コードの恵み
Knuth-Morris-Pratt algorithm

MP法とKMP法の違い
Knuth-Morris-Pratt algorithm
http://winnie.kuis.kyoto-u.ac.jp/members/okuno/Lecture/02/DataStructure/ds-02-13.pdf

指定期間人気ページランキング / 2020-5-27 → 2025-6-1
順位 ページタイトル抜粋 アクセス数
1 GitHubリモートリポジトリ名には日本語を使用できない。使用すると、ハイフンへ自動置換されてしまう | GitHub(開発環境) 1032
2 fatal: remote error: is not a valid repository name | Git BASH(開発環境) 733
3 Twitter アカウント管理 | Twitter Developer(Twitter) 616
4 Twitter API | Twitter API (Twitter) 590
5 動画対応 | プログラミング 589
6 開発 0 584
7 「Twitterデータ」対応 | Twitter Developer(Twitter) 550
8 本 | ブックマーク 444
9 Windows10で使用できるGitクライアント | GitHub(開発環境) 443
10 Webサービス | ブックマーク 420
11 マッチングサービス | Webサービスビジネス 403
12 同じ携帯電話番号でも、複数の「Twitter Developers」アカウントを作成可能 | Twitter Developer(Twitter) 352
13 TwitterOAuth では、画像URL を指定した画像投稿は出来ない(と思う)。ライブラリを使用しなければ出来るから、Twitter API の制限ではない(と思われる)  | Twitter 317
14 技術書籍 | プログラミング 299
15 teratailでは質問しない | プログラミング 292
15 気になった動画 | ブックマーク 292
16 埋め込みツイート | Twitter Developer(Twitter) 271
17 個人事業主 | Webサービスビジネス 250
18 Twitter 電話番号の問題 | Twitter Developer(Twitter) 231
19 コインチェック株式会社   | Webサービスビジネス 199
2025/6/2 1:02 更新