新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのような印象を受けました。 そこで、この記事でZ-algorithmに絞った説明、実際の挙動の説明、実装例を紹介します。 以下のページ、PDFを参考にしてます。 snuke.hatenablog.com 文字列アルゴリズム from HCPC: 北海道大学競技プログラミングサークル www.slideshare.net Z-algorithmで何ができるか? 文字列Sに対して、S[i : j]という記号を、Sのi番目からj番目(いずれも0-idx)までの連続部分文字列とします。 例えば、S="abcde"で S[1 :
![Z-algorithm詳解と具体例 - Senの競技プログラミング備忘録](https://cdn-ak-scissors.b.st-hatena.com/image/square/34b6ead94e68fb349dccbceb3d6ecab49a1650c8/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2FS%2FSen_comp%2F20200116%2F20200116170247.jpg)