hdu2896(AC自动机)
程序员文章站
2022-06-06 20:56:47
...
这个题有一个非常坑的点 就是网址不一定是小写字母!!
还有就是这个题卡空间卡到令人窒息 子节点数组开到130即可 节点最大个数210*500即可
但是要注意不是小写字母的话下文代码处原本的s[j]-'a'要变为s[j]-'\0'
(不如叫RE-ME-WA自动机好了)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
const int maxn = 210*500;
char str[10000+100];
vector<int>res;
struct node{
int fail;
int cnt;
int next[130];
}tree[maxn];
bool vis[maxn];
int k =0,ans = 0;
queue<int>q;
map<int,int>mp;
void build_tree(int id, char *s, int bi){
int len = strlen(s);
for(int i =0;i<len;++i){
int j =s[i]-'\0';
if(tree[id].next[j]==0){
tree[id].next[j]=++k;
}
id = tree[id].next[j];
}
mp[id] = bi;
tree[id].cnt++;
}
void build_fail(int id){
while(!q.empty())q.pop();
for(int i =0;i<130;++i){
int j =tree[id].next[i];
if(j){
q.push(j);
tree[j].fail = id;
}
}
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = 0;i<130;++i){
int j = tree[now].next[i];
if(j==0){
tree[now].next[i] = tree[tree[now].fail].next[i];
continue;
}
tree[j].fail = tree[tree[now].fail].next[i];
q.push(j);
}
}
}
void solve(int id, char *s){
int len = strlen(s),j=0;
for(int i =0;i<len;++i){
int j = tree[id].next[s[i]-'\0'];
while(j&&!vis[j]){
ans+=tree[j].cnt;
if(tree[j].cnt){
res.push_back(mp[j]);
}
vis[j]=true;
j = tree[j].fail;
}
id = tree[id].next[s[i]];
}
}
int main(){
int n;
scanf("%d",&n);
for(int i =1;i<=n;++i){
scanf("%s",str);
build_tree(0,str,i);
}
build_fail(0);
int m;
scanf("%d",&m);
int total = 0;
int c= 1;
while(m--){
// cout<<c<<endl;
//
memset(vis,false,sizeof(vis));
res.clear();
ans = 0;
scanf("%s",str);
solve(0,str);
if(ans){
sort(res.begin(),res.end());
cout<<"web "<<c<<":";
for(int i =0;i<res.size();++i){
cout<<" "<<res[i];
}
cout<<endl;
total++;
}
c++;
}
cout<<"total"<<":"<<" "<<total<<endl;
}
上一篇: 数据结构之循环队列
下一篇: 数据结构之数组实现环形队列