题意:给你n个模式串,再给你m个主串,问你每个主串中有多少模式串,并输出是哪些。注意一下,这里给的字符范围是可见字符0~127,所以要开130左右。
思路:用字典树开的时候储存编号,匹配完成后set记录保证不重复和排序。
代码:
#include<cstdio>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
const int maxn = 5000000+5;
const int maxm = 100000+5;
const int MOD = 1e7;
const int INF = 0x3f3f3f3f;
const int kind = 130;
const char baset = 0;
using namespace std;
struct Trie{
Trie *next[kind];
Trie *fail; //失配值
int sum; //以此为单词结尾的个数
int id;
Trie(){
sum = 0;
memset(next,NULL,sizeof(next));
fail = NULL;
id = 0;
}
};
Trie *root;
queue<Trie *> Q;
int head,tail;
set<int> record;
void Insert(char *s,int id){
Trie *p = root;
for(int i = 0;s[i];i++){
int x = s[i] - baset;
if(p ->next[x] == NULL){
p ->next[x] = new Trie();
}
p = p ->next[x];
}
p ->sum++;
p ->id = id;
}
void buildFail(){ //计算失配值
while(!Q.empty()) Q.pop();
Q.push(root);
Trie *p,*temp;
while(!Q.empty()){
temp = Q.front();
Q.pop();
for(int i = 0;i < kind;i++){
if(temp ->next[i]){
if(temp == root){ //父节点为root,fail为root
temp ->next[i] ->fail = root;
}
else{
p = temp ->fail; //查看父节点的fail
while(p){
if(p ->next[i]){
temp ->next[i] ->fail = p ->next[i];
break;
}
p = p ->fail;
}
if(p == NULL) temp ->next[i] ->fail = root;
}
Q.push(temp ->next[i]);
}
}
}
}
void ac_automation(char *ch){
//p为模式串指针
Trie *p = root;
int len = strlen(ch);
for(int i = 0;i < len;i++){
int x = ch[i] - baset;
while(!p ->next[x] && p != root)
p = p ->fail;
p = p ->next[x]; //找到后p指针指向该结点
if(!p) p = root; //若指针返回为空,则没有找到与之匹配的字符
Trie *temp = p;
while(temp != root){
if(temp ->id > 0)
record.insert(temp ->id);
temp = temp ->fail;
}
}
}
char ch[210];
char s[10005];
int main(){
int n,m,x;
root = new Trie();
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%s",ch);
Insert(ch,i);
}
buildFail();
int tot = 0;
scanf("%d",&m);
for(int i = 1;i <= m;i++){
record.clear();
scanf("%s",s);
ac_automation(s);
if(record.size()){
tot++;
printf("web %d:",i);
int End = record.size();
for(int j = 1;j <= End;j++){
int id = *record.begin();
printf(" %d",id);
record.erase(id);
}
printf("\n");
}
}
printf("total: %d\n",tot);
return 0;
}