Problem Description Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string p=p1p2...pm . So, he wants to generate as many as possible pattern strings from p using the following method:
1. select some indices i1,i2,...,ik such that 1≤i1<i2<...<ik<|p| and |ij−ij+1|>1 for all 1≤j<k .
2. swap pij and pij+1 for all 1≤j≤k .
Now, for a given a string s=s1s2...sn , Professor Zhang wants to find all occurrences of all the generated patterns in s . Input There are multiple test cases. The first line of input contains an integer T , indicating the number of test cases. For each test case:
The first line contains two integers n and m (1≤n≤105,1≤m≤min{5000,n}) -- the length of s and p .
The second line contains the string s and the third line contains the string p . Both the strings consist of only lowercase English letters. Output For each test case, output a binary string of length n . The i -th character is "1" if and only if the substring sisi+1...si+m−1 is one of the generated patterns. Sample Input
3
4 1
abac
a
4 2
aaaa
aa
9 3
abcbacacb
abc
Sample Output
1010
1110
100100100
题意：
有串s,p.串p可以经过一些变换，变换规则是，每个字符可以跟它前一个字符或者后一个字符交换位置。交换次数不限，但是每个字符只能交换或者被交换一次。
结果输出一个n位的二进制，对于匹配串的字符位置i，如果s的子串（si,si+1,si+2,...,si+m-1）可以由p串变换得出的话，则这个位置输出“1”，否则输出“0”。
分析：
这个题目很坑，卡了常数，姿势不好就会超时。
首先很容易可以看出来这是一个dp题。dp[ i ][ k ][ j ] 表示 s[ i ] 经过 k 操作 能够跟 p[ j ] 匹配上并且 p[ j ] 之前的字符也已经匹配上了。
k = 0 ，当前字符跟之前的字符交换。
k = 1 ，当前字符不交换
k = 2 ，当前字符跟之后的字符交换。
那么状态转移为：
dp[ j ][ 0 ][ i ] = dp[ j-1 ][ 2 ][ i-1 ] && s[ i ] == p[ j-1 ]
dp[ j ][ 1 ][ i ] = ( dp[ j-1 ][ 1 ][ i-1 ] || dp[ j-1 ][ 0 ][ i-1 ]) && s[ i ] == p[ j ]
dp[ j ][ 2 ][ i ] = ( dp[ j-1 ][ 1 ][ i-1 ] || dp[ j-1 ][ 0 ][ i-1 ]) && s[ i ] == p[ j+1 ]
好我们根据这个状态转移方程式可以写出第一份代码：
代码1：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=1e5+10;
const int M=5010;
char s[N],p[M];
bool dp[M][3][N];
int main()
{
std::cout.sync_with_stdio(false);
int t,n,m;
cin >> t;
while(t--)
{
cin >> n >> m;
cin >> s >> p;
memset(dp,0,sizeof(dp));
for(int i = 0 ; i < n ; i ++)
{
if(s[i] == p[0])dp[0][1][i] = 1;
if(m > 1 && s[i] == p[1]) dp[0][2][i] = 1;
}
for(int j = 1 ; j < m ; j ++)
{
for(int i = 0; i < n ; i ++)
{
dp[j][0][i] = dp[j-1][2][i-1]&&(s[i] == p[j-1]);
dp[j][1][i] = (dp[j-1][0][i-1] || dp[j-1][1][i-1]) && (s[i] == p[j]);
if(j+1<m) dp[j][2][i] = (dp[j-1][1][i-1] || dp[j-1][0][i-1]) && (s[i] == p[j+1]);
}
}
for(int i = 0 ; i < n ; i ++)
{
if(dp[m-1][0][i+m-1] || dp[m-1][1][i+m-1]) cout << "1";
else cout << "0";
}
cout << endl;
}
return 0;
}
然而显然以上代码的时间复杂度是O(m*n) 空间复杂度是O(m*n)。先不说时间，根据m,n的范围可以知道dp[M][3][N]肯定会爆。我们仔细观察可以发现dp的递推只跟之前一个状态有关。所以我们可以使用滚动数组优化空间，使得空间复杂度变成O(n).
代码2：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=1e5+10;
const int M=5010;
char s[N],p[M];
bool dp[2][3][N];
int main()
{
std::cout.sync_with_stdio(false);
int t,n,m;
cin >> t;
while(t--)
{
cin >> n >> m;
cin >> s >> p;
memset(dp,0,sizeof(dp));
int cur = 0;
for(int i = 0 ; i < n ; i ++)
{
if(s[i] == p[0])dp[cur][1][i] = 1;
if(m > 1 && s[i] == p[1]) dp[cur][2][i] = 1;
}
for(int j = 1 ; j < m ; j ++)
{
cur ^= 1;
for(int i = 0; i < n ; i ++)
{
dp[cur][0][i] = dp[cur^1][2][i-1]&&(s[i] == p[j-1]);
dp[cur][1][i] = (dp[cur^1][0][i-1] || dp[cur^1][1][i-1]) && (s[i] == p[j]);
if(j+1<m) dp[cur][2][i] = (dp[cur^1][1][i-1] || dp[cur^1][0][i-1]) && (s[i] == p[j+1]);
}
}
for(int i = 0 ; i < n ; i ++)
{
if(dp[cur][0][i+m-1] || dp[cur][1][i+m-1]) cout << "1";
else cout << "0";
}
cout << endl;
}
return 0;
}
好，现在只剩时间了，其实这里我们需要使用一个奇计淫巧 ----------- bitset优化,
实际上根据算法大体上已经不能再优化了O(m*n).但是显然这个代码是会超时的(比赛的时候时间开的8秒。暴力可过，挂出来的题只有4秒）。
我们可以观察算法主体代码：
for(int j = 1 ; j < m ; j ++)
{
for(int i = 0; i < n ; i ++)
{
dp[j][0][i] = dp[j-1][2][i-1]&&(s[i] == p[j-1]);
dp[j][1][i] = (dp[j-1][0][i-1] || dp[j-1][1][i-1]) && (s[i] == p[j]);
if(j+1<m) dp[j][2][i] = (dp[j-1][1][i-1] || dp[j-1][0][i-1]) && (s[i] == p[j+1]);
}
内循环可以看作是每位(i)的两个数通过与、或等方式得到另一个数。注意这里强调是每一位都执行的相同操作。并且每位只有0或者1两个值。我们可以联想到位运算。
这个时候我们把dp[ j ][ k ] 看作一个bool型的数组。嗯也可以看做一个长度为N的一个二进制数。那么内层循环可以直接用位运算实现而不用循环。这样做的好处是什么呢？
它可以把时间复杂度从O(n*m) 压缩到 O(n*m/w) w是电脑的机器字长。
这里我们使用的bool数组就是bitset容器。具体优化实现看这里------------bitset优化,
代码3(AC代码)：
#include <cstdio>
#include <cstring>
#include <iostream>
#include<bitset>
using namespace std;
const int N=1e5+10;
const int M=5010;
char s[N],p[M];
bitset<N>dp[2][3];
bitset<N>w[30];
int main()
{
std::cout.sync_with_stdio(false);
int t,n,m,cur;
cin >> t;
while(t--)
{
cin >> n >> m;
cin >> s >> p;
for(int i=0;i<30;i++)
w[i].reset();
for(int i=0;i<n;i++)
w[s[i]-'a'][i]=1;
for(int i=0;i<2;i++)
for(int j=0;j<3;j++)
dp[i][j].reset();
cur=1;
dp[cur][1]=w[p[0]-'a'];
if(m>1) dp[cur][2]=w[p[1]-'a'];
for(int j=1;j<m;j++)
{
cur^=1;
// 注意这里之所以要左移1位是因为w[p[j-1]-'a']每个i是跟dp[cur^1][2]的i-1相与。所以要将右边的左移，才能使得i-1与上i.
dp[cur][0]=w[p[j-1]-'a']&(dp[cur^1][2]<<1);
dp[cur][1]=w[p[j]-'a']&((dp[cur^1][0]|dp[cur^1][1])<<1);
if(j+1<m) dp[cur][2]=w[p[j+1]-'a']&((dp[cur^1][0]|dp[cur^1][1])<<1);
}
for(int i=0;i<n;i++)
if(dp[cur][0][i+m-1]||dp[cur][1][i+m-1])
printf("1");
else
printf("0");
printf("\n");
}
return 0;
}