7K12 blog

猫でも分かるアルゴリズム解説

ABC141 E - Who Says a Pun?

f:id:tkr987:20200522204820p:plain

https://atcoder.jp/contests/abc141/submissions/11639951

f:id:tkr987:20200522211846p:plain

ZアルゴリズムはS[i]からの部分文字列が先頭S[0]からの文字列と何文字一致するか O(N)で返す。したがって、先頭インデックスをS[0]からS[N-1]まで1文字ずつずらしながらZアルゴリズムを全て試すと求めたい答えが分かる。全体計算量は O(N^2)になる。