Codeforces #299 Div1 B. Tavas and Malekas

２問目までは順当に解けました。
http://codeforces.com/contest/536/problem/B

問題

アルファベット小文字だけからなるN文字の文字列Sがあったとする。
Sの連続部分文字列でPに一致するものがM箇所あったことがわかっている。
各連続部分文字列はY[i]文字目を先頭としており、すなわちS[Y[i]..(Y[i]+|P|-1)]==Pであることがわかっている。

条件を満たすSは何通りあるか答えよ。

解法

Z algorithmを用いる。
Y[i]とY[i+1]の差が|P|以上ある場合、(Y[i]..(Y[i]+|P|-1))と(Y[i+1]..(Y[i+1]+|P|-1))は交わらないのでS[Y[i]..(Y[i]+|P|-1)]とS[Y[i+1]..(Y[i+1]+|P|-1)]の中身に依存関係はなく、互いの内容はどうであっても良い。

問題は(Y[i]..(Y[i]+|P|-1))と(Y[i+1]..(Y[i+1]+|P|-1))が交わるときである。
Y[i+1]-Y[i]=dとすると、Z algorithmの要領でPの先頭(|P|-d)文字と末尾(|P|-d)文字が一致するならそのようなY[i],Y[i+1]が存在し、そうでないならそのようなY[i],Y[i+1]は存在し得ないので解は0となる。

あとはどのY[i]に対してもS[Y[i]..(Y[i]+|P|-1)]の部分文字列に入らないような位置の文字はなんでもよいので、そのような文字の位置がq個あるなら解は26^qである。

vector<int> Zalgo(string s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	return v;
}

int N,M,L;
string P;
int Y[1010101];
int Y2[1010101];
ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>P;
	L=P.size();
	FOR(i,M) cin>>Y[i], Y2[--Y[i]]++;
	
	vector<int> V=Zalgo(P);
	
	FOR(i,M-1) if(Y[i+1]-Y[i]<L) {
		x=Y[i+1]-Y[i];
		if(V[x]!=L-x) return _P("0\n");
	}
	ll ret=1;
	x=-1;
	FOR(i,N) {
		if(Y2[i]) x=i+L;
		if(i>=x) ret=ret*26%mo;
	}
	cout<<ret<<endl;
}

まとめ

Z Algorithmを知ってるとすんなり解けるね。