border とは？

→ → → Entries ← ← ←
カテゴリー: プログラミング 　閲覧数:595　配信日: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

週間人気ページランキング ／ 7-31 → 8-6
順位 ページタイトル抜粋 アクセス数
1 開発 0 18
2 Twitter アカウント管理 | Twitter Developer(Twitter) 4
2 ソフトウェア カテゴリー 4
2 Bootstrap(デザイン) カテゴリー 4
3 Twitter API v1.1 | Twitter Developer(Twitter) 3
3 Twitter連携ログイン代替APIを探しています | Webサービス開発 3
3 「お問い合わせフォームの日本語」をどう書けば良いかが分からない | 言葉(Webサービス開発) 3
3 Git BASH 作業履歴 2022/10/21 ／ P28 site-ranking(4Th-Ranking-Service) ／ 他の「.git」ディレクトリが存在した状態のまま下記gitコマンドを実行したため、意図せず「submodule」化されてしまった例 | Git BASH(Git) 3
3 「Twitter Developers」でアプリケーションを新規作成するためには？ SMS認証用コードを確認可能な電話番号の登録が必要 | Twitter Developer(Twitter) 3
3 Git 失敗履歴2。「$ git reset」→ ソースコード削除。※Git BASH 経由で Windows10 から GitHub へ PUSH しようとするも、誤ってソースコードを削除してしまう | Git BASH(Git) 3
3 コード管理 | プログラミング 3
3 Webサービス開発 カテゴリー 3
3 Webサービス | ブックマーク 3
3 GitHubリモートリポジトリ名には日本語を使用できない。使用すると、ハイフンへ自動置換されてしまう | GitHub(Git) 3
4 Git BASH 経由で、Windows10 から GitHub へ PUSH する | GitHub(Git) 2
4 User is not Authorized の闇 | Twitter Developer(Twitter) 2
4 感想履歴(技術エントリーを見返した際に不要だと感じた「当時の感想」をこのエントリーへ移動する) | Webサービス開発 2
4 ブックマーク カテゴリー 2
4 Twitter カテゴリー 2
4 GitHub(Git) カテゴリー 2
2026/8/7 5:05 更新
指定期間人気ページランキング ／ 2020-5-27 → 2026-8-6
順位 ページタイトル抜粋 アクセス数
1 GitHubリモートリポジトリ名には日本語を使用できない。使用すると、ハイフンへ自動置換されてしまう | GitHub(Git) 1083
2 fatal: remote error: is not a valid repository name | Git BASH(Git) 754
3 開発 0 716
4 Twitter アカウント管理 | Twitter Developer(Twitter) 629
5 Twitter API | Twitter API (Twitter) 605
6 動画対応 | プログラミング 598
7 「Twitterデータ」対応 | Twitter Developer(Twitter) 569
8 Windows10で使用できるGitクライアント | GitHub(Git) 471
9 本 | ブックマーク 463
10 Webサービス | ブックマーク 435
11 マッチングサービス | Webサービスビジネス 410
12 同じ携帯電話番号でも、複数の「Twitter Developers」アカウントを作成可能 | Twitter Developer(Twitter) 374
13 TwitterOAuth では、画像URL を指定した画像投稿は出来ない(と思う)。ライブラリを使用しなければ出来るから、Twitter API の制限ではない(と思われる)　 | Twitter 334
14 技術書籍 | プログラミング 308
14 teratailでは質問しない | プログラミング 308
15 気になった動画 | ブックマーク 300
16 埋め込みツイート | Twitter Developer(Twitter) 278
17 個人事業主 | Webサービスビジネス 256
18 ログイン 251
19 Twitter 電話番号の問題 | Twitter Developer(Twitter) 248
2026/8/7 5:05 更新