Codeforces #622 Div2 E. Concatenation with intersection

Codeforcesっぽい問題。
https://codeforces.com/contest/1313/problem/E

問題

2つのN文字の文字列A,Bと、M文字の文字列Sが与えられる。
AとBそれぞれ1文字以上の部分文字列を選ぶとき、以下の条件を満たすのは何通りか。

• AとBで選ぶ区間が共通部分を持たない。
• 選んだ部分文字列を並べるとSに一致する。

解法

以下を考える。
L(i) := Aのi文字目を先頭とする部分文字列のうちSのprefixと最長何文字一致するか
R(i) := Bのi文字目を末尾とする部分文字列のうちSのsuffixと最長何文字一致するか

区間加算可能なBITを準備し、BにSのsuffixをp文字分抽出可能な末尾が何通りあるか数えられるようにしよう。
Aのi文字目を先頭とするケースでは、Bの(i+M-1)文字目以降を末尾とする部分文字列のうちR(v)が(M-L[i])以上のvの数だけ解になる。
iを走査しながら、Bのうち処理対象外になった箇所を減算しつつBITを使って対象を数え上げて行こう。

int N,M;
string A,B,S;
ll sum[1505050];

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry;
	}
	V total(int entry) {
		if(entry<0) return 0;
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry;
		return e*v0+v1;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1));
		update(R+1,-val,val*R);
	}
};
BIT_r<ll,23> bt;

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);
		}
	}
	v.push_back(0);
	return v;
}
int R[3030303];
int L[3030303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>A>>B>>S;
	
	B=B+"$"+S;
	reverse(ALL(B));
	auto X=Zalgo(B);
	FOR(i,N+1) R[N-i]=X[M+1+i];
	
	A=S+"$"+A;
	X=Zalgo(A);
	ll ret=0;
	FOR(i,M) bt.add(M-R[i],M+1,1);
	FOR(i,N+1) {
		L[i]=min(X[M+1+i],M-1);
		bt.add(M-R[i],M+1,-1);
		ret+=bt.total(L[i])-bt.total(0);
		bt.add(M-R[i+M],M+1,1);
	}
	cout<<ret<<endl;
	
	
}

まとめ

Zalgorithmがうまく使える問題は気持ちいいよね。