文字列アルゴリズム
- ローリングハッシュ
- 文字列をハッシュ化をするもの
- 詳しくはこっち
- Suffix Array
- 接尾辞配列
- 全文探索、パターンマッチングに使える
- LCP
- ある2つの文字列について接頭語がどれだけ一致しているか
- 複数文字列があるとき、ある任意の2つのLCPを求めたい場合は、「1.文字列を昇順ソート」「2.隣り合う文字列でLCPを計算」「3.ある任意の2つの間のLCPの中で最小のLCPがその2つの文字列のLCP」参考
- KMP
- KMP法 : 単一文字列のマッチングアルゴリズム
- KMP法の前処理の段階でできる配列を使うと、最短の周期が取得できる 出典
- 動的KMP？（変更可能なKMP？）
- Trie, Aho-Corasick
- Suffix Automaton
- 理解してない
- 参考
- Manacher
- 参考
- A[i] := i番目を中心としたときの最長回分の半径。半径とは(全長+1)/2のこと
- O(|S|)
- Suffix Tree
- SuffixでTreeを作ったやつ 参考1 参考2
- 効率の良いアルゴリズムがある（らしい）
- メモ
- 文字列 s を cyclic に回転させた時の辞書順最小の文字列を求める問題
- 「x + suffixの最大値は最大値」つまり、辞書順最大にするには後ろから確定していく 問題
- パターンマッチングの方法で、bitsetを使う方法もある
- 26文字分bitsetを使って文字があれば1を立てておく
- 比較するときが、26文字分スライドしてANDをとってORをとったときに範囲が全部1ならOKとする手法
- O(N/64)でごり押したいときにやる
- この方法だと?のようなマジックナンバーを扱うことができる
- これがごり押せる AC Three Substrings
問題
SuffixArray,LCP
- AOJ Password（パスワード）
- パターンマッチングに使用
- AtCoder アメージングな文字列は、きみが作る！
- 考察が長く、Suffix Arrayが必要になってくるまでの道のりが分かりにくい。
- 使う場面は「ある区間の文字列の接尾語の辞書順最小のものが知りたい」
- AtCoder 部分文字列 解説
- yukicoder No.515 典型LCP
- CodeChef Blocked websites
- ECR30 Forbidden Indices
- CSA73 Strange Substring 解説
- LC Longest Duplicate Substring
（未解決）
https://kimiyuki.net/categories/suffix-array/
http://kenkoooo.hatenablog.com/entry/2016/11/17/201707
http://www.prefield.com/algorithm/string/suffix_array.html
KMP,Aho-Corasick
- yukicoder No.430 文字列検索
- UVA 10679 I Love Strings!!
- HR Path Matching
- JAG Separate String 解説
- RUPC2018 Day3 検閲により置換 (Censored String) 解説
KMP法で最短周期を取得する問題
Trie
Trie上でのdfs
Aho-Corasickで作った木上でのDP
- AOJ 2212 盗まれた宝石
- DNA Synthesizer 解説1 解説2
- 天下一プログラマーコンテスト2016本戦 C. たんごたくさん
- AOJ 2257 Sakura Poetry
- TopCoder SRM709 Med Softmatch 解説
Palindromic Tree
- SPOJ Longest Palindromic Substring
- SPOJ Number of Palindromes
- yukicoder No.263 Common Palindromes Extra 解説
- CC Shil and Suffix Palindromes
- CC Palindromeness
- http://acm.timus.ru/problem.aspx?space=276&num=3
- HR Palindromic Border
- CC RK and his partition method
Manacher
Suffix Tree
z-algorithm
