TopCoder SRM 806 : Div1 Medium MostSubstrings

ちょっと自信ないまま通してしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=16991&rd=18686

問題

文字列Sと整数Lが与えられる。
L文字のアルファベット小文字からなる文字列のうち、Sのoccurenceが最大になるものが何通りあるか求めよ。

解法

まず安直に思いつくのは下記。
f(n,a,s) := L文字のうちprefix n文字まで定めたとき、occurenceがaで、Sのprefixとn文字のsuffixが最大s文字一致するような状態における、組み合わせの数

事前にKMPの遷移テーブルを作っておけば、次に続く文字26文字を総当たりして容易に数え上げられる。
ただ、このままでは状態がO(L^2*|S|)あるので、文字種をcとして計算量がO(L^2*|S|*w)かかりTLEする。
そこで、occurenceが最大となるものを求めればよい、という条件のもとで、以下いずれかで探索空間を減らそう。

• 同じn,sに対しては、f(n,a,s)が正である最大のaのみ処理する。そうでない場合が、以後occurenceの最大値を達成することはないため。
• 同じnに対してはf(n,a,s)が正である最大のaの周辺いくつかのみ処理する。最大値より大幅にoccurenceがビハインドしている状態が、以後最大値に追い付くことはないため。

以下のコードは後者。

int stt[105][26];
const char base='a';
void CreateSTT(string& pat) {
	int x,y,z,l;
	ZERO(stt);
	l=pat.size();
	FOR(x,l+1) {
		FOR(y,26) {
			string pre=pat.substr(0,x)+(char)(base+y);
			for(z=1;z<=min(pat.size(),pre.size());z++) if(pre.substr(pre.size()-z) == pat.substr(0,z)) stt[x][y]=z;
		}
	}
}

ll from[5][105];
ll to[5][105];
const ll mo=1000000007;


class MostSubstrings {
	public:
	int count(string S, int L) {
		int N=S.size();
		CreateSTT(S);
		
		ZERO(from);
		from[0][0]=1;
		int i,x,y,c;
		FOR(i,L) {
			ZERO(to);
			
			FOR(x,4) FOR(y,101) if(from[x][y]) {
				FOR(c,26) {
					int t=stt[y][c];
					to[x+(t==N)][t]+=from[x][y];
					if(to[x+(t==N)][t]>=mo) to[x+(t==N)][t]-=mo;
				}
			}
			
			FOR(y,104) if(to[4][y]) break;
			if(y<104) {
				FOR(x,104) {
					FOR(y,4) to[y][x]=to[y+1][x];
					to[4][x]=0;
				}
			}
			
			swap(from,to);
		}
		
		ll ret=0;
		for(y=4;y>=0;y--) {
			FOR(x,101) ret+=from[y][x];
			if(ret) break;
		}
		return ret%mo;
		
		
	}
}

まとめ

本番ちょっと自信がないままエイヤでやってしまった。