【BZOJ5337】[TJOI2018]str(动态规划,哈希)
2024-10-19 07:29:44
【BZOJ5337】[TJOI2018]str(动态规划,哈希)
题面
题解
就很呆。。。
显然按层\(dp\),如果能够匹配上就进行转移,直接哈希判断是否能够匹配就好了。。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 1000000007
#define MAX 10010
#define ull unsigned long long
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
const ull base=297;
ull h[MAX],pw[MAX];
int n,m,ans,len;char s[MAX],ch[MAX];
int f[2][MAX];
ull Hash(int l,int r){return h[r]-h[l-1]*pw[r-l+1];}
int main()
{
scanf("%d",&n);scanf("%s",s+1);len=strlen(s+1);
pw[0]=1;for(int i=1;i<=len;++i)pw[i]=pw[i-1]*base;
for(int i=1;i<=len;++i)h[i]=h[i-1]*base+s[i];
int nw=1,pw=0;
for(int i=0;i<=len;++i)f[0][i]=1;
while(n--)
{
scanf("%d",&m);for(int i=0;i<=len+1;++i)f[nw][i]=0;
while(m--)
{
scanf("%s",ch+1);int l=strlen(ch+1);
ull val=0;for(int i=1;i<=l;++i)val=val*base+ch[i];
for(int i=1;i+l-1<=len;++i)if(Hash(i,i+l-1)==val)add(f[nw][i+l],f[pw][i]);
}
nw^=1;pw^=1;
}
for(int i=1;i<=len+1;++i)add(ans,f[pw][i]);
printf("%d\n",ans);
return 0;
}
最新文章
- memcache服务器端及PHP memcache扩展的安装(转载)
- javaScript的function
- linux替换文件指定字符串前面的内容
- Python成长笔记 - 基础篇 (十二)
- 十天冲刺---Day10
- Delphi面向对象编程
- Flatten Binary Tree to Linked List
- aaaa
- Android软件开发之发送短信与系统短信库解析
- 浅谈SpringMVC(一)
- iOS多线程开发之NSThread
- js 获取每月有几周,根据年月周获取该周从周一到周日的日期等方法
- 一个maven项目打多个可执行Jar文件
- UML序列图参考资料
- Linux添加系统环境变量
- Golang对文件读写操作
- 【ASP.NET 进阶】Flv视频文件在线播放示例
- ReactiveX 学习笔记(10)可连接的数据流
- C++并发编程之std::future
- Java核心知识点 --- 线程中如何创建锁和使用锁 Lock , 设计一个缓存系统
热门文章
- Git push提交时报错Permission denied(publickey)...Please make sure you have the correct access rights and the repository exists.
- scrapy之基础概念与用法
- 学习docker——命令总结
- ocrosoft 程序设计提高期末复习问题M 递归求猴子吃桃
- 高阶组件 HOC
- 三、taro路由及设计稿及尺寸单位
- 数据处理 array json 格式 转换成 数组形式
- Vue+iview实现添加删除类
- 4 Past progressive VS simple past
- Day 6-2简单的socket通信