这是一道水题

给定几个特征串和几个字符串,求每个字符串中有那几个特征码

思路:

把每个特征串放到TRIE树里(上),用AC机挂着每个串跑一遍即可。但是会出现一种情况:若B串为A串子串,则可能出现没有匹配到B串的情况。比如 ABCD 和 BC,如果用不加修饰的AC机跑,会直接把ABCD匹配了,而BC在TRIE树的另一个分支上,没有访问。所以有3个解决办法:

1.在建树前用strstr确定每个串是否为另一个串的子串(O(N4)TLE)。因此改成KMP,复杂度O(N3),然而代码量很大。

注意到方案1使用的KMP实际上是对TRIE树每个树枝进行匹配,由此不难想到:

2. 在建树时递归沿着FAIL指针向树根寻找,如果FAIL指针指向的节点为一个特征串的结尾,则将此特征添加到原节点。使用vector可以通过此题。

3.注意到题目时间限制比较宽松,因此可以在AC自动机每寻找到一个节点时递归FAIL指针,操作通方案2.

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define CHN 129
#define MX 100000
#define MXL 201
#define MXT 10001
#define KJ 32

char vir[MXL];
char web[MXT];
char data[MX];
int flag[MX];
int fail[MX];
int son[MX][CHN];
int ans[501];
int dep[100000];
int nnum;
int root=0;

void insrt(char *str,int len,int index)
{
    int now=root;
    for(int i=0;i<len;i++)
    {
        if(son[now][str[i]-KJ])
        {
            now=son[now][str[i]-KJ];
        }
        else
        {
            nnum++;
            data[nnum]=str[i];
            son[now][str[i]-KJ]=nnum;
            now=nnum;
        }
    }
    flag[now]=index;
}

int q[MXT];
int h,t;

void getfail()
{
    int now,p;
    h=t=0;
    q[0]=root;
    while(h>=t)
    {
        now=q[t];
        for(int i=0;i<CHN;i++)
        {
            if(son[now][i])
            {
                p=fail[now];
                while(p&&!son[p][i]){p=fail[p];}
                fail[son[now][i]]=(son[p][i]==son[now][i]?root:son[p][i]);
                q[++h]=son[now][i];
            }
        }
        t++;
    }
}

void query(char *str,int len)
{
    memset(ans,0,sizeof(ans));
    int now=root;
    for(int i=0;i<len;i++)
    {
        while(son[now][str[i]-KJ]==0&&now!=0)now=fail[now];
        if(flag[now])ans[flag[now]]++;
        now=son[now][str[i]-KJ];
        for(int tmp=now;tmp>0;tmp=fail[tmp])if(flag[tmp])ans[flag[tmp]]++;
    }
}

int main()
{
    int vnum,tnum,flg,totn=0;
    scanf("%d",&vnum);
    for(int i=1; i<=vnum; i++)
    {
        scanf("%s",vir);
        insrt(vir,strlen(vir),i);
    }
    getfail();
    scanf("%d",&tnum);
    for(int i=1; i<=tnum; i++)
    {
        scanf("%s",web);
        query(web,strlen(web));
        flg=0;
        for(int k=1; k<=vnum; k++)

        {
            if(ans[k])
            {
                if(flg==0)
                {
                    flg=1;
                    printf("web %d: %d",i,k);
                }
                else printf(" %d",k);
            }
        }
        if(flg==1)
        {
            puts("");
            totn++;
        }
    }
    printf("total: %d\n",totn);
    return 0;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *