はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける文字列アルゴリズム問題まとめ [ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm,Palindromic Tree]

文字列アルゴリズム

  • Suffix Array
    • 接尾辞配列
    • 全文探索、パターンマッチングに使える
  • LCP
    • ある2つの文字列について接頭語がどれだけ一致しているか
    • 複数文字列があるとき、ある任意の2つのLCPを求めたい場合は、「1.文字列を昇順ソート」「2.隣り合う文字列でLCPを計算」「3.ある任意の2つの間のLCPの中で最小のLCPがその2つの文字列のLCP」参考
  • Trie, Aho-Corasick
    • Trie : 複数文字列から作った木
    • Aho-Corasick法 : 複数文字列のマッチングアルゴリズム 資料
    • Aho-Corasick法で作った木に対してDPする典型がある
  • Z-algorithm
  • Palindromic Tree, eertree
    • 回文にまつわる色々なことができる木
    • 数え上げ問題に使える。(最大最小でも使える?)
    • 参考1 参考2 参考3
  • Suffix Automaton