AtCoder Beginner Contest 135 F - Strings of Eternity
※ほぼ解説丸写しです
解説と解説リンクのZ algorithmの記事を読んで勉強したので備忘録
問題：文字列ｓ、ｔが与えられる。ｓを任意の回数連結してできる文字列に出てくる連続する部分列で、ｔをｋ回連結した文字列と一致するものはあるか。(k>=0)。kの最大値を求めよ
読解：
問題文を崩さない程度に書き下したんですけど、わかりづらいですね
前半はｓを無限に繰り返しことを指しています。
そして、その中でｔの繰り返しが含まれるか調べることになります。
解説解法：
天下り式ではありますが、ｔと一致するｓの開始地点を全て調べれば答えが求まります。
ｔと一致する開始地点というのは
ｓのｉ文字目～ｉ+|t|-1文字目==ｔの1文字目～|t|文字目が一致することを指します
s[i:i+len(t)]==t
とも書けますね。ここでのｓは、元のｓを無限に繰り返しているとします。
この開始地点がわかれば、開始地点→終了地点+1を次の開始地点とする。と順に調べていき、最も長い場所を見つければよいです。ループがあれば無限にｔを並べることができます。
はじめにｓを十分に繰り返して並べ、文字列ｓｓを作っておきましょう。どのくらいにすればよいでしょうか。
ｓの最後の文字から|t|文字調べるためlen(ss)>=len(s)+len(t)になれば十分です。
では次に、ｔと一致するｓｓの連続する部分文字列を全て求める必要があります。
全探索ではO(len(s)*len(t))で間に合いません。
効率よく求めるアルゴリズムとしてKMP法とZ algorithmが挙げられていました。自分はZ algorithmを勉強したのでまとめておきます。
Z algorithm
このリンクをほぼ写しただけになってます。リンク内のコードを読むのが一番わかりやすくて手っ取り早いです
Z algorithmとは？
ある開始地点ｉから、接頭辞と一致する長さを求めるアルゴリズムです。
文字列str=”abcaaabc”を考えると
Z[0]=str.size()：先頭なので当然すべて一致します。Z algorithmでは考えません
Z[1]=0：1文字目ｂは、先頭のａと一致しないので０です
Z[3]=1：3文字目ａは先頭のａと一致します。次の文字ａは2文字目のｂと一致しないのでZ[3]は１です
Z[5]=3：5~7文字目はabcと、先頭3文字と一致するので３になります
このように定義された大きさstr.size()の配列ZをO(str.size())で求めることができるのが、Z algorithmです
本問ではｔとｓｓを出現しない区切り文字を間に入れて連結します
t+'$'+ss
こうすることで、接頭辞ｔと一致する箇所をO(|t|+|ss|)で見つけることができます
Z[i]==|t|なら一致します。
$はｔにもssにも出現しないので、Z[i]>|t|にはなりません
読んだ感じ、上の元の考え方より、下の繋げて一致する場所を探すほうが使いそうですね。知らんけど
アルゴリズム
1．0から順に調べる。いま区間 [ L,R ) が一致しているとして、Ｒを右側に増やしていく。はじめは[0,0)。ｉを調べ終わった後、L,Rを初期化せずにi+1に進みます
2．もし、ｉがＲより小さい。ｉを既に調べているとき
k=i-Lとすると下に示した部分文字列が一致しています
L…i…R-1
0…k…R-L-1
0...Z[k]
L～R-1は①で調べた通り、先頭と一致します
またk～は、長さZ[k]だけ先頭と一致します。
2-1．Z[k]<R-L-1-k+1=R-i
上の2行目と3行目を比べたとき、3行目のほうが短いことを指します
このときZ[k]+1～R-L-1は、①でkを調べたときに既に調べています。L～R-1が一致するので確かです。
したがって、Z[k]がZ[k]+1文字目で不一致だと言っているので、もう一度調べる必要がなく
Z[i]=Z[k]
が導けます
2-2．Z[k]>=R-i
このとき、Z[k]からR-L文字目とR-L-1-k文字目は一致することがわかります。（ただしR-LがZ[k]以下ならば)
しかし、R-L文字目と、R文字目は違うため、R文字目からは未知です。
なので①と同じ同様にしてRを伸ばして調べていきます
おそらくですが、Z[k]＞R-iならば、Z[i]=R-iになりそうな気がします。
Z[k]==R-iのとき、調べる必要がありそうですね。
わけても計算量はほぼ変わらないのでわける意味がなさそうです。もしくは自分がわからないところでコーナーがありそう（多分後者）
3．i>Rのとき
これは、Z[i-1]=0だったりすると起こります。
L=R=iで初期化して①の操作をします。
全てのｉで1～3をすればよいです。
以上がZ algorithmです。わかってしまえば実装量は多くないので楽でした
本問の実装
この問題にZ algorithmをどう適用したかを書いて終わろうと思います
・|ss|>=|s|+|t|となるｓの繰り返しｓｓを求める
・str=t+'$'+ssとその長さの配列Zを用意。Z algorithmを使う
このあと、有向辺(u,v)を作ります。
Z[(u-|t|-1)%|s|]=|t|となるuで、v=(u+|t|-|t|-1)%|s|です
ここでssのindexとZのindexが|t|+1個ズレていることに注意
sに落とし込むことでループを見つけやすくしています。
また、同じ辺から2つの別の頂点に辺ができることはありません。
最長パスを求める過程ですが、全探索っぽいですかね。名前つけられない
dist=［ｉを最後のｔとするｔの繰り返し回数］
初期値-1です。
visited=[false]*|s|
探索済みかどうかを記録します
for (i=0~s.size){
探索済みならcontinue
探索済みに変える
もし、出る辺がないならdist[i]=-1のまま
あるならdist[i]=0
int now=i;
while (辺があるなら){
もし最初のiに戻れば無限
距離を大きい方に更新できるなら更新して
now=edge[now]と更新
探索済みに変える
更新できないならbreak;
}
}
基本は距離更新したときだけ進むだけです。最悪ケースでも2|s|くらいのループで済んでると思います、たぶん
最後に、distの最大値を出力して終わりです。
感想：
Z algorithm面白かったです。なんかよく使いそうだけど、自分じゃ絶対思いつけないみたいなアルゴリズム良いですね
まあ名前ついてるアルゴリズムって大体そうだと思いますけど
まだ定着してないのでそらで書けるようにしときたいです。おつしゅ
