想定解が想定外だった。
https://atcoder.jp/contests/abc141/tasks/abc141_e
問題
文字列Sが与えられる。
ここから重ならない位置から取った2つの部分文字列が一致する最長の長さを求めよ。
解法
始点がLずれた2つの部分文字列のprefixが、最長何文字一致するかLを総当たりしよう。
F(i) := i文字目を始点とする部分文字列と、(i+L)文字目を始点とする部分文字列が最長何文字一致するか
とする。S[i]==S[i+L]ならF(i)=F(i+1)+1だし、そうでなければF(i)=0ということで、iの多い順に求めていこう。
F(i)の最大値が解の候補となるが、重ならないという条件よりmin(max(F(i)),L)を求めよう。
int N; string S; int dp[5050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; int ma=0; for(int len=N;len>=1;len--) { ZERO(dp); for(x=N-len-1;x>=0;x--) { if(S[x]!=S[x+len]) dp[x]=0; else dp[x]=min(dp[x+1]+1,len); ma=max(ma,dp[x]); } } cout<<ma<<endl; }
まとめ
Z-Algorithmでも計算量変わらないし、AtCoderの500ptでこれを想定解にしてくるのが意外。