CF613E Puzzle Lover

题意

英文版题面

<style>
    .input-output-copier {
        font-size: 1.2rem;
        float: right;
        color: #888 !important;
        cursor: pointer;
        border: 1px solid rgb(185, 185, 185);
        padding: 3px;
        margin: 1px;
        line-height: 1.1rem;
        text-transform: none;
    }

    .input-output-copier:hover {
        background-color: #def;
    }

    .test-explanation textarea {
         100%;
        height: 1.5em;
    }
</style>

Oleg Petrov loves crossword puzzles and every Thursday he buys his favorite magazine with crosswords and other word puzzles. In the last magazine Oleg found a curious puzzle, and the magazine promised a valuable prize for it's solution. We give a formal description of the problem below.

The puzzle field consists of two rows, each row contains n cells. Each cell contains exactly one small English letter. You also are given a word w, which consists of k small English letters. A solution of the puzzle is a sequence of field cells c₁, ..., c_k, such that:

For all i from 1 to k the letter written in the cell c_i matches the letter w_i;
All the cells in the sequence are pairwise distinct;
For all i from 1 to k - 1 cells c_i and c_i + 1 have a common side.

Oleg Petrov quickly found a solution for the puzzle. Now he wonders, how many distinct solutions are there for this puzzle. Oleg Petrov doesn't like too large numbers, so calculate the answer modulo 10⁹ + 7.

Two solutions c_i and c'_i are considered distinct if the sequences of cells do not match in at least one position, that is there is such j in range from 1 to k, such that c_j ≠ c'_j.

Input

The first two lines contain the state of the field for the puzzle. Each of these non-empty lines contains exactly n small English letters.

The next line is left empty.

The next line is non-empty and contains word w, consisting of small English letters.

The length of each line doesn't exceed 2 000.

Output

Print a single integer — the number of distinct solutions for the puzzle modulo 10⁹ + 7.

Examples

Input

Copy

code
edoc

code

Output

Copy

Input

Copy

aaa
aaa

aa

Output

Copy

            </div>

阿狸的矩阵字符串匹配

Background

阿狸利用糖果稠密度分析仪得到了许多糖果，也终于成功地离开了基环内向树森林。刚走出森林的他却又落入了魔法陷阱之中。陷阱中有一个写满字母的矩阵，似乎只有找到合适的不重复路径，并在上面走一遍，才能解除陷阱。

可是合适的路径到底是什么呢？阿狸摇晃着自己的小脑袋，只感觉有水在流动，思考似乎成了奢侈的事，魔法陷阱中的 debuff 太强了。

Description

阿狸所看到的是一个 2×N 的矩阵 A，矩阵中每个格子都是一个小写字母。同时，你得到了长度为 M 一个字符串 S，你需要在矩阵中找到一条不重复路径（起点和终点任意），使得依次经过的字母连起来恰好是 S，求这样的路径有多少种。

你只能向上、向下、向左或向右走，不能斜着走或跳着走，也不能走出矩阵外或重复经过同一个点。两种路径不同，当且仅当至少有一个时刻所在的位置不同。

由于答案可能很大，你只要输出答案对 (10^9+7) 取模的值即可。

Input

第一行和第二行两行长度相同的字符串描述 2×N 的矩阵 A。
第三行一个空行。
第四行一个字符串，表示 S。

Output

一个正整数表示答案对 (10^9+7) 取模后的值。

Sample Input1

code
edoc

code

Sample Output1

Sample Input2

aaa
aaa

Sample Output2

Sample Explanation

Data Limitation
对于测试点 1，保证 N≤5。
对于测试点 2~3，保证 N≤10。
对于测试点 4，保证 N≤20。
对于测试点 5~6，保证 N≤50。
对于测试点 7~8，保证 N≤300。
对于测试点 9~10，保证 N≤1,000。
对于测试点 11~12，保证 S 是一个全 a 字符串，且 A 也是全 a 的矩阵。
对于测试点 13~14，保证 S 是一个全 a 字符串。
对于测试点 15~16，保证 S 是一个形如 abbbb…的仅由一个字符 a 和若干字符 b 组成
的字符串。
对于 100%的数据，保证 (1≤N,M≤2×10^3)。

分析

(2 imes N)的矩阵，总的折返次数不会超过2，分成左中右三部分分别处理。

可以发现不重复经过同一个格子的路径一定是形如这样的：

这个路径可以分成三段：
➢ 从 S 出发向左走一段再回来。
➢ 上下上下地往右走。
➢ 往右走一段再回到 T。
当然，S 和 T 的位置可以调换。

发现这个性质之后就可以直接 DP 了，左右两段可以用字符串 Hash 做，Left[i][j][k]表示匹配到第 i 行第 j 列的位置，匹配了 k 个字符的方案，那么 Left[i][j][k]的转移就是Left[i][j][k]=Left[i][j-1][k]+1；Right[i][j][k]表示匹配到第 i 行第 j 列的位置，匹配了 k 个字符的方案，那么 Right[i][j][k]的转移就是 Right[i][j][k]= Right[i][j+1][k]+1。接着中间的一段用简单的 DP 实现，设 F[i][j][k]表示在第 i 行第 j 列的位置，匹配到第 k 个字符的方案，把三段拼起来就好了。这题就这么简单，主要是细节处理上比较麻烦。

总复杂度是 (O(N^2))。

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int N=2020,P1=1e9+7,P2=1e9+9;
int n,m,ans;
int tm1[N],tm2[N],tm1_[N],tm2_[N];
int f[2][N][N];
struct dd{ // double hash
	int x,y;
	bool operator==(co dd&n)co {return x==n.x&&y==n.y;}
}t1,t2,t3,t4;
struct cc{
	char s[N];
	int len,pre1[N],pre2[N],suf1[N],suf2[N];
	void read(){
		scanf("%s",s+1),len=strlen(s+1);
		for(int i=1;i<=len;++i){
			pre1[i]=((ll)tm1[i-1]*s[i]+pre1[i-1])%P1;
			pre2[i]=((ll)tm2[i-1]*s[i]+pre2[i-1])%P2;
		}
		for(int i=len;i;--i){
			suf1[i]=((ll)tm1[len-i]*s[i]+suf1[i+1])%P1;
			suf2[i]=((ll)tm2[len-i]*s[i]+suf2[i+1])%P2;
		}
	}
	dd get_hash(int l,int r){
		dd t;
		if(l<=r){
			t.x=(ll)tm1_[l-1]*(pre1[r]+P1-pre1[l-1])%P1;
			t.y=(ll)tm2_[l-1]*(pre2[r]+P2-pre2[l-1])%P2;
		}
		else{ // upside down
			t.x=(ll)tm1_[len-l]*(suf1[r]+P1-suf1[l+1])%P1;
			t.y=(ll)tm2_[len-l]*(suf2[r]+P2-suf2[l+1])%P2;
		}
		return t;
	}
}s1,s2,w;
int ksm(int x,int y,int P){
	int z=1;
	for(;y;y>>=1,x=(ll)x*x%P)
		if(y&1) z=(ll)z*x%P;
	return z;
}
void init(){
	int n=2000;
	tm1[0]=tm2[0]=tm1_[0]=tm2_[0]=1;
	for(int i=1;i<=n;++i) tm1[i]=31LL*tm1[i-1]%P1,tm2[i]=31LL*tm2[i-1]%P2;
	tm1_[n]=ksm(tm1[n],P1-2,P1),tm2_[n]=ksm(tm2[n],P2-2,P2);
	for(int i=n-1;i;--i) tm1_[i]=31LL*tm1_[i+1]%P1,tm2_[i]=31LL*tm2_[i+1]%P2;
	s1.read(),s2.read(),w.read();
}
int main(){
//	freopen("string.in","r",stdin),freopen("string.out","w",stdout);
	init();
	n=s1.len,m=w.len;
	// forward
	f[0][n+1][0]=f[1][n+1][0]=1; // right
	for(int i=n;i;--i){
		f[0][i][0]=f[1][i][0]=1;
		for(int k=2;k+k<=m&&i+k-1<=n;++k){ // length starts with 2
			t1=s1.get_hash(i,i+k-1),t2=s2.get_hash(i,i+k-1);
			t3=w.get_hash(m,m-k+1),t4=w.get_hash(m-k-k+1,m-k);
			if(t1==t3&&t2==t4) f[1][i][k+k]=1;
			if(t2==t3&&t1==t4) f[0][i][k+k]=1;
		}
	}
	for(int i=n;i;--i) // middle
		for(int k=1;k<=m;++k){
			if(s1.s[i]==w.s[m-k+1]) (f[0][i][k]+=f[0][i+1][k-1])%=P1;
			if(s2.s[i]==w.s[m-k+1]) (f[1][i][k]+=f[1][i+1][k-1])%=P1;
			if(k>1&&s1.s[i]==w.s[m-k+1]&&s2.s[i]==w.s[m-k+2]) (f[0][i][k]+=f[1][i+1][k-2])%=P1;
			if(k>1&&s2.s[i]==w.s[m-k+1]&&s1.s[i]==w.s[m-k+2]) (f[1][i][k]+=f[0][i+1][k-2])%=P1;
		}
	for(int i=1;i<=n+1;++i){
		(ans+=f[0][i][m])%=P1;
		(ans+=f[1][i][m])%=P1;
		for(int k=2;k+k<=m&&k<i;++k){ // left
			t1=s1.get_hash(i-k,i-1),t2=s2.get_hash(i-k,i-1);
			t3=w.get_hash(k,1),t4=w.get_hash(k+1,k+k);
			if(t1==t3&&t2==t4) (ans+=f[1][i][m-k-k])%=P1;
			if(t2==t3&&t1==t4) (ans+=f[0][i][m-k-k])%=P1;
		}
	}
	if(m==1) return printf("%d
",ans),0; // no inverse
	memset(f,0,sizeof f);
	f[0][n+1][0]=f[1][n+1][0]=1;
	for(int i=n;i;--i){
		f[0][i][0]=f[1][i][0]=1;
		for(int k=2;k+k<m&&i+k-1<=n;++k){ // <m to avoid repeating
			t1=s1.get_hash(i,i+k-1),t2=s2.get_hash(i,i+k-1);
			t3=w.get_hash(1,k),t4=w.get_hash(k+k,k+1);
			if(t1==t3&&t2==t4) f[1][i][k+k]=1;
			if(t2==t3&&t1==t4) f[0][i][k+k]=1;
		}
	}
	for(int i=n;i;--i)
		for(int k=1;k<=m;++k){
			if(s1.s[i]==w.s[k]) (f[0][i][k]+=f[0][i+1][k-1])%=P1;
			if(s2.s[i]==w.s[k]) (f[1][i][k]+=f[1][i+1][k-1])%=P1;
			if(m>2&&k>1&&s1.s[i]==w.s[k]&&s2.s[i]==w.s[k-1]) (f[0][i][k]+=f[1][i+1][k-2])%=P1; // m>2 to AR
			if(m>2&&k>1&&s2.s[i]==w.s[k]&&s1.s[i]==w.s[k-1]) (f[1][i][k]+=f[0][i+1][k-2])%=P1;
		}
	for(int i=1;i<=n+1;++i){
		(ans+=f[0][i][m])%=P1;
		(ans+=f[1][i][m])%=P1;
		for(int k=2;k+k<m&&k<i;++k){ // <m to AR
			t1=s1.get_hash(i-k,i-1),t2=s2.get_hash(i-k,i-1);
			t3=w.get_hash(m-k+1,m),t4=w.get_hash(m-k,m-k-k+1);
			if(t1==t3&&t2==t4) (ans+=f[1][i][m-k-k])%=P1;
			if(t2==t3&&t1==t4) (ans+=f[0][i][m-k-k])%=P1;
		}
	}
	return printf("%d
",ans),0;
}