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

hamayanhamayan's blog

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

文字列アルゴリズム

  • Suffix Array
    • 接尾辞配列
    • 全文探索、パターンマッチングに使える
  • LCP
    • ある2つの文字列について接頭語がどれだけ一致しているか
    • 複数文字列があるとき、ある任意の2つのLCPを求めたい場合は、「1.文字列を昇順ソート」「2.隣り合う文字列でLCPを計算」「3.ある任意の2つの間のLCPの中で最小のLCPがその2つの文字列のLCP」参考
  • KMP
    • KMP法 : 単一文字列のマッチングアルゴリズム
    • KMP法の前処理の段階でできる配列を使うと、最短の周期が取得できる 出典
  • Aho-Corasick
    • Aho-Corasick法 : 複数文字列のマッチングアルゴリズム 資料
    • Aho-Corasick法で作った木に対してDPする典型がある
  • Z-algorithm
    • よく知らない