文字列マッチング - taq225's Memo on Algorithms

文字列マッチング

#Algorithm #String

Abstract

Zアルゴリズムで前処理をすることで, 文字列$ Tを$ Sとパターンマッチさせることができる.

Explanation

文字列$ Tを$ Sとパターンマッチさせるときは, $ Tに含まれない文字を$ \#として, 連結した文字列$ T \# Sに対してZアルゴリズムを適用する.

$ Z[i] = |T| となるインデックス$ i > |T|から始まる部分文字列の接頭辞が$ Tと一致することがわかる.

References