首页 > > 程序设计 > C/C++ >

hdu 6096---String（AC自动机）

2018-06-17 21:58:45来源：未知阅读 ()

题目链接

Problem Description

Bob has a dictionary with N words in it.
Now there is a list of words in which the middle part of the word has continuous letters disappeared. The middle part does not include the first and last character.
We only know the prefix and suffix of each word, and the number of characters missing is uncertain, it could be 0. But the prefix and suffix of each word can not overlap.
For each word in the list, Bob wants to determine which word is in the dictionary by prefix and suffix.
There are probably many answers. You just have to figure out how many words may be the answer.

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each test case contains two integer N and Q, The number of words in the dictionary, and the number of words in the list.
Next N line, each line has a string Wi, represents the ith word in the dictionary (

Output

For each test case, output Q lines, an integer per line, represents the answer to each word in the list.

Sample Input

4 4

aba

cde

acdefa

cdef

a a

cd ef

ac a

ce f

Sample Output

题意：有 n 个由小写字母构成的串，现在有q次询问，每次给一个前缀和后缀，求这n个串中有多少个串满足给的前缀和后缀，前缀和后缀不能在这个字符串中重叠？

思路：对于给的n个串s[i]，修改为 s[i] = s[i] + "_" + s[i] ,对于每次询问输入的前缀pre和后缀suf,修改为str=suf+"_"+pre，对这q次询问的前缀后缀构成的串构建tire树，然后用AC自动机匹配跑一下即可。但是这样会存在冗余，例如：aaa，前缀aa 后缀aa，那么也会匹配上，所以比较时还得判断一下长度。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
using namespace std;
const int N=1e5+5;
string s[N];
struct Node{
    Node *son[30];
    Node *fail;
    int flag;
    int len;
}tr[6*N];
Node *root;
queue<Node*>Q;
int ans[N];
vector<int>v[N];
int tot;

void init()
{
    tot=0;
    memset(ans,0,sizeof(ans));
    root=&tr[0];
    while(!Q.empty()) Q.pop();
    for(int i=0;i<N;i++) v[i].clear();
    for(int i=0;i<6*N;i++)
    {
        tr[i].flag=0;
        tr[i].fail=NULL;
        for(int j=0;j<30;j++) tr[i].son[j]=NULL;
    }
}
void build(string s,int id)
{
    Node *now=root;
    for(int i=0;i<s.length();i++)
    {
       int x=s[i]-'_';
       if(!now->son[x]) now->son[x]=&tr[++tot];
       now=now->son[x];
    }
    if(now->flag) {
        v[now->flag].push_back(id);
        return ;
    }
    now->flag=id;
    now->len=s.length();
}
void setFail()
{
    Q.push(root);
    while(!Q.empty())
    {
        Node *now=Q.front(); Q.pop();
        for(int i=0;i<30;i++)
        {
            if(now->son[i])
            {
                Node *p=now->fail;
                while(p && (!(p->son[i]))) p=p->fail;
                now->son[i]->fail=(p)?p->son[i]:root;
                Q.push(now->son[i]);
            }
            else now->son[i]=(now!=root)?now->fail->son[i]:root;
        }
    }
}
void query(string s)
{
    Node *now=root;
    int len=s.length();
    for(int i=0;i<len;i++)
    {
        int x=s[i]-'_';
        now=now->son[x];
        Node *p=now;
        while(p!=root)
        {
            if(p->flag && p->len<=len/2+1) ans[p->flag]++;
            p=p->fail;
        }
    }
}
int main()
{
    int T; cin>>T;
    while(T--)
    {
        init();
        int n,q; scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];
            s[i]=s[i]+"_"+s[i];
        }
        for(int i=1;i<=q;i++)
        {
            string s1,s2; cin>>s1>>s2;
            string ss=s2+"_"+s1;
            build(ss,i);
        }
        setFail();
        for(int i=1;i<=n;i++)
        {
            query(s[i]);
        }
        for(int i=1;i<=q;i++)  ///处理相同的前后缀;
        {
            for(int j=0;j<v[i].size();j++)
                ans[v[i][j]]=ans[i];
        }
        for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    }
    return 0;
}