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

时间:2021-09-23 01:58:03

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<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm 5005
bitset<maxn>dp[][];
bitset<maxn>f[];
int n,m;
char s[maxn],p[maxm]; void init(){//处理f数组
for(int i=;i<;i++)f[i].reset();
for(int j=;j<n;j++)f[s[j]-'a'][j]=;
} int main(){
int t;cin>>t;
while(t--){
scanf("%d%d",&n,&m);
scanf("%s%s",&s,&p);
init();
for(int i=;i<;i++)
for(int j=;j<;j++)
dp[i][j].reset();
//处理初始状态:即p[0]或p[1] 和s[1..j]的匹配
dp[][]=f[p[]-'a'];
if(m>) dp[][]=f[p[]-'a']; //然后刷表从p[1]转移到p[m] ,滚动数组节省空间
int cur=;
for(int i=;i<m;i++){
cur^=;
dp[cur][]=(dp[cur^][]<<) & f[p[i-]-'a'];//这里为什么要用<<1,因为是把dp[i-1][j-1]的答案用到dp[i][j]里,等于集体左移了一次
dp[cur][]=((dp[cur^][] | dp[cur^][])<<) & f[p[i]-'a'];
if(i<m-)
dp[cur][]=((dp[cur^][] | dp[cur^][])<<) & f[p[i+]-'a'];
} for(int i=;i<n;i++)
if(dp[cur][][i+m-] || dp[cur][][i+m-])cout<<;
else cout<<;
puts("");
}
}

字符串匹配dp+bitset,滚动数组优化——hdu5745(经典)的更多相关文章

  1. dp,滚动数组优化

    51Nod1084矩阵取数问题 V2 题意: 一个M*N矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,先从左上走到右下,再从右下走到左上.第1遍时只能向下和向右走,第2遍时只能向上和向左 ...

  2. NOIP2008 传纸条(DP及滚动数组优化)

    传送门 这道题有好多好多种做法呀……先说一下最暴力的,O(n^4的做法) 我们相当于要找两条从左上到右下的路,使路上的数字和最大.所以其实路径从哪里开始走并不重要,我们就直接假设全部是从左上出发的好啦 ...

  3. HDU&lowbar;1024&period;MaxSumPlusPlus&lpar;基础DP &plus; 滚动数组优化讲解&rpar;

    这道题打破了我常规的做题思路,因为这是我刚开始训练DP,感觉这道题目好晕眼呀,emm其实就是感觉自己是真的菜...... 为什么说打破了我的做题思路呢,因为我平时看题解都是在已经AC或者完全不懂的情况 ...

  4. &lbrack;BZOJ1044&rsqb;&lbrack;HAOI2008&rsqb;木棍分割 二分 &plus; 单调队列优化dp &plus; 滚动数组优化dp

    Description 有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长 ...

  5. LG3004 「USACO2010DEC」Treasure Chest 区间DP&plus;滚动数组优化

    问题描述 LG3004 题解 把拿走的过程反向,看做添加的过程,于是很显然的区间DP模型. 设\(opt_{i,j}\)代表区间\([i,j]\)中Bessie可以获得的最大值,显然有 \[opt_{ ...

  6. CodeForces 173C Spiral Maximum 记忆化搜索 滚动数组优化

    Spiral Maximum 题目连接: http://codeforces.com/problemset/problem/173/C Description Let's consider a k × ...

  7. 51nod 编辑距离 &plus; 滚动数组优化

    这道题一开始觉得增加和删除会移动字符串的位置很不好做 两个字符串dp状态一般是第一个前i个和第二个前j个 #include<cstdio> #include<algorithm&gt ...

  8. HDU - 1024 Max Sum Plus Plus 最大m段子段和&plus;滚动数组优化

    给定n个数字,求其中m段的最大值(段与段之间不用连续,但是一段中要连续) 例如:2 5 1 -2 2 3 -1五个数字中选2个,选择1和2 3这两段. dp[i][j]从前j个数字中选择i段,然后根据 ...

  9. poj1159 dp&lpar;滚动数组优化)

    H - 简单dp 例题扩展 Crawling in process... Crawling failed Time Limit:3000MS     Memory Limit:65536KB     ...

随机推荐

  1. AngularJs项目文件以及文件夹结构

    app/ ----- Libs/ // references for all libs ---------- angular.js ---------- angular-route.js ----- ...

  2. ubuntu 15&period;10 install nvidia driver

    先添加源sudo add-apt-repository ppa:graphics-drivers/ppa 更新一下:sudo apt-get update (附原始链接:http://www.omgu ...

  3. mysql Integer Types &lpar;Exact Value&rpar; - INTEGER&comma; INT&comma; SMALLINT&comma; TINYINT&comma; MEDIUMINT&comma; BIGINT

    使用mysql的时候,用到int类型的蛮多,需要注意一下: 1. 值的范围 Type Storage Minimum Value Maximum Value   (Bytes) (Signed/Uns ...

  4. android开发 PopupWindow 设置充满屏幕

    View qrcode_view = this.getLayoutInflater().inflate(R.layout.taskdetail_qrcode,null); final PopupWin ...

  5. TCP&sol;IP 与OSI结构图

    OSI参考模型各层的作用 物理层:在物理媒体上传输原始的数据比特流. 数据链路层:将数据分成一个个数据帧,以数据帧为单位传输.有应有答,遇错重发. 网络层:将数据分成一定长度的分组,将分组穿过通信子网 ...

  6. codeforces C&period; Restore Graph

    题意:构造一个有n个顶点,每个点度不超过k,然后给出每一个点到达一个定点的最短距离d数组,然后构造出这样的一个图: 思路:排序之后,有两个距离为0的或者没有直接输出-1,然后用两个游动下表,后面的与前 ...

  7. Oracle sql执行计划

    explain plan     explain plan for sql_statement     select * from table(dbms_xplan.display) DBMS_XPL ...

  8. Linux 软件安装到 &sol;usr,&sol;usr&sol;local&sol; 还是 &sol;opt 目录区别

    Linux 的软件安装目录是也是有讲究的,理解这一点,在对系统管理是有益的 /usr:系统级的目录,可以理解为C:/Windows/, /usr/lib理解为C:/Windows/System32./ ...

  9. IOS高级开发之多线程(四)NSOperation

    1.什么是NSOperation,NSOperationQueue? NSOperation是一个抽象的基类,表示一个独立的计算单元,可以为子类提供有用且线程安全的建立状态,优先级,依赖和取消等操作. ...

  10. gitbook editor教程

    用户首先需要安装 nodejs,以便能够使用 npm 来安装 gitbook.所以我们先安装node.js,安装过程很简单,都是不断按下「Next」按钮就可以了 写node -h可以看看是否安装成功 ...