字符串匹配dp+bitset，滚动数组优化——hdu5745(经典)

/*
dp[i,j][0|1|2]表示p串的第i位，s串的第j位相匹配，pi和pi-1换，pi不换，pi和pi+1换的状态下是否能匹配
dp[i,j][0] = dp[i-1,j-1][2] & p[i-1]==s[j]
dp[i,j][1] = (dp[i-1,j-1][1] || dp[i-1,j-1][2]) & p[i]==s[j] 
dp[i,j][2] = (dp[i-1,j-1][0] || dp[i-1,j-1][1]) & p[i+1]==s[j]

由于dp是01数组，并且dp[i]的所有状态都由dp[i-1]得到，所以我们可以考虑用bitset优化j
观察原来的dp方程 
dp[i][0]由dp[i-1][2] 
*/
#includeusing namespace std;
#define maxn 100005
#define maxm 5005
bitsetdp[3][3];
bitsetf[26];
int n,m;
char s[maxn],p[maxm];

void init(){//处理f数组 
    for(int i=0;i26;i++)f[i].reset();
    for(int j=0;j‘a‘][j]=1;
}

int main(){
    int t;cin>>t;
    while(t--){
        scanf("%d%d",&n,&m);
        scanf("%s%s",&s,&p);
        init();
        for(int i=0;i2;i++)
            for(int j=0;j3;j++)
                dp[i][j].reset();
        //处理初始状态：即p[0]或p[1] 和s[1..j]的匹配 
        dp[0][1]=f[p[0]-‘a‘];
        if(m>1) dp[0][2]=f[p[1]-‘a‘]; 
        
        //然后刷表从p[1]转移到p[m] ,滚动数组节省空间 
        int cur=0;
        for(int i=1;i){
            cur^=1;
            dp[cur][0]=(dp[cur^1][2]1) & f[p[i-1]-‘a‘];//这里为什么要用
            dp[cur][1]=((dp[cur^1][1] | dp[cur^1][0])1) & f[p[i]-‘a‘];
            if(i1) 
                dp[cur][2]=((dp[cur^1][1] | dp[cur^1][0])1) & f[p[i+1]-‘a‘]; 
        }
        
        for(int i=0;i)
            if(dp[cur][1][i+m-1] || dp[cur][0][i+m-1])cout1;
        else cout0;
        puts("");
    }
}