模板題
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define KIND 128
#define M 10010
struct node
{
node *fail;
node *next[KIND];
int id;
node ()
{
fail = NULL;
id = 0;
memset(next, 0, sizeof(next));
}
};
char ch[M];
queue<node *> q;
vector<int> g;
void insert(node *&root, char *ch, int id)
{
node *p = root;
int i = 0, t;
while(ch[i])
{
t = ch[i] - 31;
if(!p->next[t]) p->next[t] = new node();
p = p->next[t];
i++;
}
p->id = id;
}
void AC(node *&root)
{
q.push(root);
while(!q.empty())
{
node *p = NULL;
node *t = q.front();
q.pop();
for(int i = 0; i < KIND; i++)
{
if(t->next[i])
{
p = t->fail;
while(p)
{
if(p->next[i])
{
t->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if(!p) t->next[i]->fail = root;
q.push(t->next[i]);
}
}
}
}
bool query(node *&root, char *ch, int count)
{
g.clear();
int i = 0, t, top = 0, flag = 0;
node *p = root, *tmp;
while(ch[i])
{
t = ch[i] - 31;
while(!p->next[t] && p != root) p = p->fail;
p = p->next[t];
if(!p) p = root;
tmp = p;
while(tmp != root && tmp->id)
{
flag = 1;
g.push_back(tmp->id);
tmp = tmp->fail;
}
i++;
}
if(!flag) return false;
sort(g.begin(), g.end());
printf("web %d:", count);
printf(" %d", g[0]);
for(int i = 1; i < g.size(); i++)
{
if(g[i] != g[i - 1])
printf(" %d", g[i]);
}
printf("\n");
return true;
}
int main()
{
int n, total;
while(~scanf("%d", &n))
{
node *root = new node();
total = 0;
for(int i = 0; i < n; i++)
{
scanf("%s", ch);
insert(root, ch, i + 1);
}
AC(root);
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%s", ch);
if(query(root, ch, i + 1)) total++;
}
printf("total: %d\n", total);
}
return 0;
}