[HOJ 182][COCI 2011/2012 #5]hh盜墓記

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

先備知識: Trie、AC自動機
這題的意思就是: 找出每個字串Li在S裡面符合的每一個位置，覆蓋上去(不影響以後的匹配)，求未被覆蓋的字母數
由於S長度到300000，Li有5000個，要把這些Li建成一個AC自動機才不會TLE
可是Li長度最多又到5000，這樣普通的AC自動機最多要"5000*5000*26=6.5億"的空間，就爆了XD
所以，Trie空間要省著用，這裡我利用map動態開點，當然，用head[]和nxt[]這種指標方式滑來滑去(?)也可以
然後這個Trie裡面存字串長度就好了，這樣在匹配到的時候就可以直接算出並記錄下覆蓋區間
最後，把區間排序，求總覆蓋長度，用N減掉即可

code:

#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
void getmax(int &a,const int b){if(b>a)a=b;}
struct Trie
{
    vector<map<char,int> >CH;
    vector<int>LEN;
    void clear(){CH.clear(),LEN.clear();Expand();}
    void Expand(){CH.push_back(map<char,int>()),LEN.push_back(0);}
    int GetNxt(const int u,const char c)
    {
        const auto it=CH[u].find(c);
        if(it==CH[u].end())
        {
            const int sz=CH.size();
            Expand();
            return CH[u][c]=sz;
        }
        else return it->second;
    }
    void Insert(char *s)
    {
        int u=0,i=0;
        for(;s[i];i++)u=GetNxt(u,s[i]);
        LEN[u]=i;
    }
    vector<int>FAIL;
    void GetFail()
    {
        FAIL.clear(),FAIL.resize(CH.size(),0);
        queue<int>q;
        for(const auto &it:CH[0])q.push(it.second);
        while(!q.empty())
        {
            const int u=q.front();q.pop();
            for(const auto &it:CH[u])
            {
                const int nxt=it.second;
                int f=FAIL[u];
                while(f&&CH[f].find(it.first)==CH[f].end())f=FAIL[f];
                const auto result=CH[f].find(it.first);
                FAIL[nxt]=(result==CH[f].end()?0:result->second);
                getmax(LEN[nxt],LEN[FAIL[nxt]]);
                q.push(nxt);
            }
        }
    }
    struct Segment
    {
        int l,r;
        Segment(){}
        Segment(const int _l,const int _r):l(_l),r(_r){}
        bool operator<(const Segment &s)const{return l<s.l;}
    };
    int Solve(const char *str)
    {
        vector<Segment>segs;
        int u=0;
        for(int i=0;str[i];i++)
        {
            auto it=CH[u].find(str[i]);
            while(u&&it==CH[u].end())it=CH[u=FAIL[u]].find(str[i]);
            if(it!=CH[u].end())
            {
                u=it->second;
                if(LEN[u])segs.push_back(Segment(i-LEN[u]+1,i+1));
            }
        }
        sort(segs.begin(),segs.end());
        int ans=0,cur=0;
        for(Segment &seg:segs)
        {
            if(cur<seg.l)cur=seg.l;
            if(cur<seg.r)ans+=seg.r-cur,cur=seg.r;
        }
        return ans;
    }
}TRIE;
int N;
char S[300001];
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%s",&N,S)==2)
    {
        TRIE.clear();
        if(true)
        {
            int m;
            char *tmp=new char[5001];
            scanf("%d",&m);
            while(m--)scanf("%s",tmp),TRIE.Insert(tmp);
            delete[]tmp;
        }
        TRIE.GetFail();
        printf("%d\n",N-TRIE.Solve(S));
        break;
    }
    return 0;
}