社区讨论
这个数据?
P3808AC 自动机(简单版)参与者 5已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mikdevng
- 此快照首次捕获于
- 2025/11/29 22:12 3 个月前
- 此快照最后确认于
- 2025/12/01 19:25 3 个月前
警示后人:记得在 中调用处理 指针的函数。
CPP#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e6+5;
int n;
string s[N],t;
struct ACt{
struct Node{
int ch[27];
int fail;
int flag;
Node(){
memset(ch,0,sizeof ch);
fail=flag=0;
}
}tr[N];
int tot=0;
void insert(string s){
int p=0;
for(char c:s){
int to=c&31;
if(!tr[p].ch[to]) tr[p].ch[to]=++tot;
p=tr[p].ch[to];
}
tr[p].flag++;
}
void prepare(){
queue<int> q;
int p=0;
q.push(p);
while(!q.empty()){
int u=q.front();
q.pop();
if(u==0){
for(int i=1;i<=26;i++)
if(tr[u].ch[i]) q.push(tr[u].ch[i]);
continue;
}
for(int i=1;i<=26;i++)
if(tr[u].ch[i]){
int v=tr[u].ch[i];
q.push(v);
p=tr[u].fail;
while(p&&!tr[p].ch[i]) p=tr[p].fail;
if(tr[p].ch[i]) tr[v].fail=tr[p].ch[i];
else tr[v].fail=0;
}
}
}
int run(string s){
int cnt=0,p=0;
for(char c:s){
int to=c&31;
cnt+=tr[p].flag;
tr[p].flag=0;
while(p&&!tr[p].ch[to]){
p=tr[p].fail;
cnt+=tr[p].flag;
tr[p].flag=0;
}
if(tr[p].ch[to]) p=tr[p].ch[to];
cnt+=tr[p].flag;
tr[p].flag=0;
}
return cnt;
}
}act;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
act.insert(s[i]);
}
cin>>t;
cout<<act.run(t);
return 0;
}
打完后忘了在 中加 ,结果还过了 ,害得我找了半天 指针的问题才发现没把 打进去。。。
回复
共 4 条回复,欢迎继续交流。
正在加载回复...