Codeforces #282 Div1 B. Obsessive String

先日ローリングハッシュのライブラリ作っておいたのでまぁまぁすんなり解けた。
http://codeforces.com/contest/494/problem/B

問題

文字列Sから、互いに重複しない1つ以上の連続部分文字列を取り出す。
各連続部分文字列がTをsubstringに持つような取り出し方は何組あるか答えよ。

解法

KMPまたはローリングハッシュを使った文字列一致判定とDPを活用する。
Sにおいて、S[0..x]までの範囲における解をDPで順に求める。

y≦(x-|T|+1)かつS[y...y+|T|-1]==Tを満たすy、すなわちS[y..x]がTを含むような最大のyを求める。
するとz≦yであるS[z...x]もTを含むし、その際はS[0..(z-1)]における解の数だけS[z..x]と取り出すパターンが得られる。

以下のコードでは、以下のように二重に累積和を取って処理している。

• dp[x]: z≦yとなるS[z..x]となる取り出し方を伴う分け方の数。これはsum2[y]に等しい。
• sum[x]: dp[0]～dp[x]の和。すなわち、各S[0]～S[x]を右端とする取り出し方を伴う分け方の数。
• sum2[x]: sum[0]～sum[x]の和。S[z..x]を取り出すなら、その左側の組み合わせはsum[0]+sum[1]+...+sum[z-1]となるので、累積和を取った置いた方が良い。

struct RollingHash {
	static const ll mo0=1000000007,mo1=1000000009;
	static const ll mul0=10009,mul1=10007;
	static const ll add0=1000010007, add1=1003333331;
	string s; int l;
	vector<ll> hash_[2],pmo_[2],pmor_[2];
	void init(string s) {
		this->s=s; l=s.size(); int i,j;
		hash_[0].push_back(0); pmo_[0].push_back(1);
		hash_[1].push_back(0); pmo_[1].push_back(1);
		FOR(i,l) pmo_[0].push_back(pmo_[0].back()*mul0%mo0);
		FOR(i,l) pmo_[1].push_back(pmo_[1].back()*mul1%mo1);
		FOR(i,l) hash_[0].push_back((hash_[0].back()*mul0+add0+s[i])%mo0);
		FOR(i,l) hash_[1].push_back((hash_[1].back()*mul1+add1+s[i])%mo1);
	}
	pair<ll,ll> hash(int l,int r) { // s[l..r]
		pair<ll,ll> p=make_pair(hash_[0][r+1]+(mo0-hash_[0][l]*pmo_[0][r+1-l]%mo0),
							    hash_[1][r+1]+(mo1-hash_[1][l]*pmo_[1][r+1-l]%mo1));
		if(p.first>=mo0) p.first-=mo0;
		if(p.second>=mo1) p.second-=mo1;
		return p;
	}
};

string S,T;
int LS,LT;
ll mo=1000000007;
RollingHash sh,th;
int ok[100010];
ll dp[100010];
ll sum[100010];
ll sum2[100010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	LS=S.size();
	LT=T.size();
	
	sh.init(S);
	th.init(T);
	pair<ll,ll> ph=th.hash(0,LT-1);
	FOR(i,LS-(LT-1)) ok[i]=ph==sh.hash(i,i+(LT-1));
	
	dp[0]=sum[0]=sum2[0]=1;
	int lo=-1;
	FOR(i,LS) {
		if(i-(LT-1)>=0 && ok[i-(LT-1)]) lo=i-(LT-1);
		
		if(lo>=0) dp[i+1]=sum2[lo]%mo;
		sum[i+1]=(sum[i]+dp[i+1])%mo;
		sum2[i+1]=(sum2[i]+sum[i+1])%mo;
	}
	cout<<(sum[LS]+(mo-1))%mo<<endl;
	
}

まとめ

多重な累積和のDPはややこしいよね。