hdu5726

题目大意 :
         在母串里面找子串，字串可以变化，询问所有匹配位置

        其实是一个dp，设状态dp[i][j][0]表示母串匹配到i子串匹配到 j，且子串最后一个字符与前面的字符交换， dp[i][j][1]不交换，dp[i][j][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];
然后bitset暴力压缩掉一维，滚动数组又压缩掉一个维度。
要注意biset压缩掉大的那一维度，滚动数组压缩掉第二大的维度才能过，压反了就tle了。

#include<bits/stdc++.h>
using namespace std;

const int MAXS=1e5+5,MAXP=5e3+5;
char s[MAXS],p[MAXP];
bitset<MAXS> dp[2][3];
bitset<MAXS> s_char[26];


int main(){
    int n,m,T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %s %s",&n,&m,s,p);
        for(int i=0;i<26;i++)s_char[i].reset();
        for(int i=0;i<n;i++)s_char[s[i]-'a'][i]=1;
        
        
        int t=1;
        
        dp[t][0][0]=0;
        dp[t][1][0]=s[0]==p[0];
        dp[t][2][0]=s[0]==p[1];
        for(int i=1;i<n;i++){
            dp[t][0][i]=0;
            dp[t][1][i]=s[i]==p[0];
            dp[t][2][i]=s[i]==p[1];
            }
        t^=1;
        
        for(int j=1;j<m;j++){
            
            dp[t][0] =  (dp[t^1][2]<<1) & s_char[p[j-1]-'a'];
            dp[t][1] = ( (dp[t^1][1]|dp[t^1][0]) << 1 ) & s_char[p[j]-'a'];
            if(j+1<m)dp[t][2] = ((dp[t^1][1]|dp[t^1][0])<<1) & s_char[p[j+1]-'a'];
            else dp[t][2].reset();
            
            dp[t][0][0] = 0;
            dp[t][1][0] = 0;
            dp[t][2][0] = 0;
            
            t^=1;
            }
        
        
        
        for(int i=m-1;i<n;i++){
            printf("%d",(dp[t^1][0][i]|dp[t^1][1][i]));
            }
        for(int i=0;i<m-1;i++){
            printf("0");
            }
        cout<<endl;
        }
    }
//000001
//0000011

<