Codeforces #853 : Div2 F. Serval and Brain Power

ちょっと手間取ったけど本番中に解き切れた。
https://codeforces.com/contest/1789/problem/F

問題

文字列Tがパワフルであるとは、Tがある文字列を2回以上繰り返した形である場合を意味する。
N文字の文字列Sが与えられる。Sの(連続でなくてもよい)部分文字列のうち、パワフルなものの最大長を答えよ。

解法

まず、文字列を2回繰り返したケースを列挙しよう。
Sを前と後ろに2分割した際、両者のLCSを取ればよい。これは分割位置を総当たりしながら行ってもO(N^3)なので十分間に合う。

あとは同じ文字列が3回以上繰り返すケースである。
最初の1回分の文字列をDFSの要領で総当たりし、そのつどその文字列をSの部分列で3回以上繰り返せるか判定することで枝刈りしていく。

int N;
string S;
int nex[81][26];
int ma;

int dpdp[81][81];

int lcs(string& AA,string& BB) {
	int x,y,ma=0;
	ZERO(dpdp);
	
	FOR(x,AA.size()) FOR(y,BB.size()) {
		if(AA[x]==BB[y]) dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x][y]+1);
		dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x][y+1]);
		dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x+1][y]);
		ma=max(ma,dpdp[x+1][y+1]);
	}
	return ma;
}

void dfs(int cur,string& C) {
	if(cur) {
		int step=C.size();
		int num=0;
		int c=cur;
		while(c<N+1) {
			c=nex[c][C[num]];
			if(c==N+1) break;
			step++;
			num++;
			if(num==C.size()) num=0;
		}
		
		if(step<3*C.size()) return;
		ma=max(ma,(int)(step/C.size()*C.size()));
	}
	int i;
	FOR(i,26) {
		int ne=nex[cur][i];
		if(ne+2*(C.size()+1)<=N&&C.size()+1+(N-ne)>ma) {
			C.push_back(i);
			dfs(ne,C);
			C.pop_back();
		}
		
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,N) {
		string a=S.substr(0,i+1);
		string b=S.substr(i+1);
		ma=max(ma,lcs(a,b)*2);
	}
	
	FOR(i,26) nex[N][i]=N+1;
	FORR(c,S) c-='a';
	for(i=N-1;i>=0;i--) {
		FOR(j,26) nex[i][j]=nex[i+1][j];
		nex[i][S[i]]=i+1;
	}
	
	string C;
	dfs(0,C);
	cout<<ma<<endl;
}

まとめ

想定解は4回繰り返しまでは特別扱いして、5回については上記手段を取ることだったっぽいね。