首页 技术 正文
技术 2022年11月23日
0 收藏 829 点赞 5,014 浏览 1534 个字

BY 九野

做了一道题,用我的那种写法华丽丽的超时了。,无奈学一学数组实现的

#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
const int maxnode=250*1000+10000;//maxnode=单词数*单词长度+常数
const int sg_size=26;
struct Trie
{
int ch[maxnode][sg_size];
int val[maxnode];//该单词在模式串出现的次数
int last[maxnode];
int f[maxnode];//失配函数
int num[maxnode];//该单词在文本串中出现的次数
int pre[maxnode];//该单词的前驱
int len[maxnode];//以该单词结尾的单词长度
int Char[maxnode];//该单词相应的字母
int road[maxnode];//路径压缩优化,针对模式串出现的种类
int sz;
int newnode()
{
val[sz]=f[sz]=last[sz]=len[sz]=num[sz]=0;
memset(ch[sz],0,sizeof(ch[sz]));
return sz++;
}
void init()
{
sz=0;
newnode();
}
int idx(char c)
{
return c-'A';
}
int insert(char *s)
{
int u=0,i;
for(i=0;s[i];i++)
{
int c=idx(s[i]);
if(!ch[u][c])
ch[u][c]=newnode();
pre[ch[u][c]]=u;
Char[ch[u][c]]=s[i];
len[ch[u][c]]=len[u]+1;
road[ch[u][c]]=1;
u=ch[u][c];
}
val[u]=1;
num[u]=0;
return u;
}
void getfail()
{
queue<int>q;
int i;
for(i=0;i<sg_size;i++)
{
if(ch[0][i])
q.push(ch[0][i]);
}
int r,c,u,v;
while(!q.empty())
{
r=q.front();
q.pop();
for(c=0;c<sg_size;c++)
{
u=ch[r][c];
if(u)
continue;
q.push(u);
v=f[r];
while(v&&ch[v][c]==0)
v=f[v];//沿失配边走上去 假设失配后有节点 且 其子节点c存在则结束循环
f[u]=ch[v][c];
}
}
}
void find(char *s)
{ //计算模式串出现的个数:(每种多次出现算多次)
int j=0;
for(int i=0;s[i];i++)
{
int c=idx(s[i]);
while(j&&ch[j][c]==0)
j=f[j];
j=ch[j][c];
int temp=j;
while(temp)
{
num[temp]++;
temp=f[temp];
}
}
}
void find_kind(char *s,int &ans)
{
//计算种数, 反复出现的不再计算(若多个询问则要在此处加for(i=0->sz)lu[i]=1;
int j=0,i,c,temp;
for(i=0;s[i];i++)
{
c=idx(s[i]);
while(j&&ch[j][c]==0)
j=f[j];
j=ch[j][c];
temp=j;
while(temp&&road[temp])
{
if(val[temp])
{
++ans;
val[temp]=0;
}
road[temp]=0;
temp=f[temp];
}
}
}
}ac;
int main()
{}

上一篇: POJ 2486
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:8,241
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,110
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:5,913
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,725
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,969
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,404