Codeforces #238 Div2. C. Running Track

またグダグダでした。
http://codeforces.com/contest/615/problem/C

問題

文字列S,Tが与えられる。
Sの連続部分文字列、またはそれを反転させたものを連結し、Tを作成したい。
最小何個のSの部分文字列が必要か。

解法

LCSの要領で、Tの各位置を先頭とする部分文字列と、Sの各位置を先頭とする部分文字列が最小何文字一致するか求めておく(Sを反転させたものも同様)。
あとは貪欲にSの部分文字列またはそれを反転させたもののうち、Tのprefixとの一致長が最長となるものを取り除くことを繰り返す。

string S,T;
int LS,LT;

int LC[2][2120][2120];

void solve() {
	int i,j,k,l,x,y; string s;
	
	cin>>S>>T;
	LS=S.size();
	LT=T.size();
	
	for(x=LS-1;x>=0;x--) for(y=LT-1;y>=0;y--) {
		if(S[x]==T[y]) LC[0][x][y]=LC[0][x+1][y+1]+1;
		if(S[LS-1-x]==T[y]) LC[1][x][y]=LC[1][x+1][y+1]+1;
	}
	
	vector<pair<int,int>> R;
	int cur=0;
	while(cur<LT) {
		int ma=0;
		pair<int,int> p;
		FOR(y,LS) {
			if(LC[0][y][cur]>ma) ma=LC[0][y][cur], p=make_pair(y,y+ma-1);
			if(LC[1][y][cur]>ma) ma=LC[1][y][cur], p=make_pair(LS-1-y,LS-1-y-(ma-1));
		}
		cur+=ma;
		if(ma==0) return _P("-1\n");
		R.push_back(p);
	}
	
	_P("%d\n",R.size());
	FORR(r,R) _P("%d %d\n",r.first+1,r.second+1);
	
	
}

まとめ

本番無駄にローリングハッシュ使ってTLEした。