Separate String
Separate String
时间限制: 1 Sec 内存限制: 128 MB
提交: 50 解决: 16
题目描述
For example, the following 4 separation methods satisfy the condition when t=abab and S={a,ab,b}.
a,b,a,b
a,b,ab
ab,a,b
ab,ab
Your task is to count the number of ways to separate t. Because the result can be large, you should output the remainder divided by 1,000,000,007.
输入
N
s1
:
sN
t
The first line consists of an integer N (1≤N≤100,000) which is the number of the elements of S. The following N lines consist of N distinct strings separated by line breaks. The i-th string si represents the i-th element of S. si consists of lowercase letters and the length is between 1 and 100,000, inclusive. The summation of length of si (1≤i≤N) is at most 200,000. The next line consists of a string t which consists of lowercase letters and represents the string to be separated and the length is between 1 and 100,000, inclusive.
输出
样例输入
3
a
b
ab
abab
样例输出
4 题解:在kuangbin的板子当中增加ln(以此为结尾的字符串的长度),true_nex(也可以叫做true_fail,用于表示真正有效的fail值,即存在以此为结尾的字符串)数组;
true_nex数组层层计算即可,因为上层的true_nex肯定已被正确计算。然后在query函数里面跑一个简单的DP即可。 AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+;
const int maxn=1e6+;
ll dp[maxn];
struct Trie
{
int nxt[][],fail[],endd[],ln[],true_nex[];
int root,L;
int newnode(){
for(int i=;i<;i++){
nxt[L][i]=-;
}
true_nex[L]=;
ln[L]=;
endd[L++]=;
return L-;
}
void init(){
L=;
root=newnode();
}
void insert(char buf[])
{
int len=strlen(buf);
int now=root;
for(int i=;i<len;i++){
if(nxt[now][buf[i]-'a']==-){
nxt[now][buf[i]-'a']=newnode();
ln[nxt[now][buf[i]-'a']]=ln[now]+;
}
now=nxt[now][buf[i]-'a'];
}
endd[now]++;
}
void build()
{
queue<int> Q;
fail[root]=root;true_nex[root]=root;
for(int i=;i<;i++){
if(nxt[root][i]==-){
nxt[root][i]=root;
}
else{
fail[nxt[root][i]]=root;
true_nex[nxt[root][i]]=root;/**/
Q.push(nxt[root][i]);
}
}
while(!Q.empty())
{
int now=Q.front();
Q.pop();
for(int i=;i<;i++)
{
if(nxt[now][i]==-){
nxt[now][i]=nxt[fail[now]][i];
}
else{
fail[nxt[now][i]]=nxt[fail[now]][i];
if(endd[nxt[fail[now]][i]]>) true_nex[nxt[now][i]]=nxt[fail[now]][i];/**/
else true_nex[nxt[now][i]]=true_nex[nxt[fail[now]][i]];/**/
Q.push(nxt[now][i]);
}
}
}
}
ll query(char buf[])
{
int len=strlen(buf);
int now=root;
int res=;
dp[]=;
for(int i=;i<len;i++)
{
now=nxt[now][buf[i]-'a'];
int temp=now;
while(temp!=root)
{
dp[i+]=(dp[i+]+dp[i+-ln[temp]]*endd[temp])%mod;
temp=true_nex[temp];
}
}
return dp[len];
}
}ac;
int n;
char buf[maxn];
int main()
{
int t=;
for(;t;t--)
{
scanf("%d",&n);
ac.init();
while(n--)
{
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
scanf("%s",buf);
printf("%lld\n",ac.query(buf));
}
return ;
}
最新文章
- The Solution of UESTC 2016 Summer Training #1 Div.2 Problem C
- Docker入门简介
- mysql连接报错 Host &lsquo;xxx&rsquo;is blocked because of many connection errors;unblock with 'mysqladmin flush-hosts'
- NHibernate系列文章十四:NHibernate事务
- OVER Clause是个好东西,常和ROW_NUMBER()、Sum、AVG、Count、Min、Max配合使用
- MFC源码不能设置断点调试
- oracle中查询含字母的数据[正则表达式]
- html readonly和disabled的区别
- Unable to find &#39;struts.multipart.saveDir&#39; property setting.
- 计蒜客模拟赛D2T3 蒜头君救人:用bfs转移状压dp
- javascript常用函数实现的收集
- heartbeat单独提供高可用服务
- eclipse中打断点debug无效
- MT【284】构造函数的导数的两类题型
- maven jdk 版本配置
- Python学习——多线程,异步IO,生成器,协程
- shell编程awk基础介绍
- xlrd与xlwt的下载
- TZOJ 2018 SPF(连通图割点和分成的连通块)
- 双缓冲队列解决WPF界面卡死
热门文章
- Spring Cloud Eureka(四):Eureka 配置参数说明
- Difference Between static and default methods in interface
- centos6.9实现双网卡绑定
- R语言:实现SQL的join功能的函数
- redis2. sds 字符串(SimpleDynamicString)
- Java:基础知识点
- 基于MybatisUtil工具类,完成CURD操作
- PCL中有哪些可用的PointT类型(3)
- mybaits及mybaits generator 插件使用指南(亲测原创)
- spark简单快速学习及打开UI界面---1