kmjp's blog

競技プログラミング参加記です

AtCoder ABC #141 : E - Who Says a Pun?

想定解が想定外だった。
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でこれを想定解にしてくるのが意外。