bitset的经典优化，即把可行性01数组的转移代价降低

bitset的适用情况，当内层状态只和外层状态的上一个状态相关，并且内层状态的相关距离是一个固定的数，可用bitset，换言之，能用滚动数组是能用bitset优化的前提

/*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]<<1 & p[i-1]和s[1..j] 得到 dp[i][1]由dp[i-1][1|2]<<1 & p[i]和s[1..j] 得到dp[i][2]由dp[i-1][0|1]<<1 & p[i+1]和s[1..j] 得到 那么我们再预处理一下s数组和26个字符比较的bitset数组即可 */#include
     
      using namespace std;#define maxn 100005#define maxm 5005bitset
      
       dp[3][3];bitset
       
        f[26];int n,m;char s[maxn],p[maxm];void init(){
   //处理f数组     for(int i=0;i<26;i++)f[i].reset();    for(int j=0;j
        
         >t;    while(t--){        scanf("%d%d",&n,&m);        scanf("%s%s",&s,&p);        init();        for(int i=0;i<2;i++)            for(int j=0;j<3;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