学步园

很久没有自己敲一个题了,这道又WA得我内!牛!满!面!啊......不过还是得这样才印象深刻.

记得检查输入是否正确.不要焦躁.

AC了之后感觉忽然有了力量~

题意:给出许多模式串,一个源码,求源码中都有哪些模式串出现了,分别出现几次.

思路:AC_Automation中,注意模式串之间有重叠的情况,就是无论是否匹配到了当前串的末尾,都要借助一个tmp指针往回找一遍,看看别的链上是否有可以匹配的.一直找到根为止.

对于输出要求,首先trie树的尾节点标记id为输入序号,从0开始.同时准备一个结构体数组,按照id顺序存病毒名和出现次数.

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int n;
inline int GetId(char c)
{
    return c - 'A';
}
typedef struct virus
{
    string name;
    int freq;
}virus;
class node{
public:
    node *chd[26];
    node *fail;
    int id;

    node(){
        memset(chd,0,sizeof(chd));
        fail = NULL;
        id = -1;
    }
};

class AC_Automation
{
public:
    node *root;
    queue <node*> q;
    virus v[1005];

    AC_Automation(){
        root = new node;
        while(!q.empty())   q.pop();
        for(int i=0;i<n;i++)
            v[i].freq = 0;
    }
    void insert(string s,int th)
    {
        node *cur = root;
        int len = s.length();
        for(int i=0;i<len;i++)
        {
            int index = GetId(s[i]);
            if(!cur->chd[index])      cur->chd[index] = new node;
            cur = cur->chd[index];
        }
        cur->id = th;
        v[th].name = s;
    }
    void BuildAC()
    {
        node *cur,*tmp;
        q.push(root);
        while(!q.empty())
        {
            cur = q.front();
            q.pop();
            for(int i=0;i<26;i++)
            {
                if(cur->chd[i])
                {
                    if(cur == root)     cur->chd[i]->fail = root;
                    else
                    {
                        tmp = cur->fail;
                        while(tmp->fail && !tmp->chd[i])   tmp = tmp->fail;///*
                        if(tmp->chd[i])     cur->chd[i]->fail = tmp->chd[i];
                        else    cur->chd[i]->fail = root;
                    }
                    q.push(cur->chd[i]);
                }
            }
        }
    }
    void query(string s)
    {
        node *cur = root,*tmp;///shers
        int len = s.length();
        for(int i=0;i<len;i++)
        {
            int index = GetId(s[i]);
            if(index<0 ||index>=26)
            {
                cur = root;//puts("here");
                continue;
            }
            if(cur->chd[index]) cur = cur->chd[index];
            else
            {
                while(cur && !cur->chd[index])     cur =  cur->fail;///*
                if(!cur)    cur = root;
                if(cur->chd[index])     cur = cur->chd[index];
            }
            tmp = cur;
            while(tmp->fail)///为了处理相互重叠或相互包含的情况
            {
                if(tmp->id > -1)
                    v[tmp->id].freq++;
                tmp = tmp->fail;

            }
        }
    }
    void PrintRes()
    {
        for(int i=0;i<n;i++)
        {
            if(v[i].freq)   cout<<v[i].name<<": "<<v[i].freq<<endl;
        }
    }
};
char pat[52],tar[2000005];

int main()
{
    while(scanf("%d",&n)==1)
    {
        AC_Automation AC;
        getchar();
        for(int i=0;i<n;i++)
        {
            gets(pat);
          //  cout<<"pat "<<pat<<endl;
            AC.insert(pat,i);
        }
        AC.BuildAC();
        gets(tar);
       // cout<<"tar "<<tar<<endl;
        AC.query(tar);

        AC.PrintRes();
    }
}