dp+bitset优化

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; }