[POJ 3415]Common Substrings (題解一)

從這題，我們已經知道在枚舉$B$的前綴$B_{p}$時，如何求出$B_{p}$最長的後綴，使得這個後綴同時也是$A$的子字串
方法就是讓$B$在$A$的後綴自動機裡面轉移，同時維護目前答案的長度 (稱作$len$)

那要怎麼求出節點$u$代表的最長字串在$A$裡面出現幾個地方呢？
就是「代表$A$的前綴的節點集合」中，有幾個可以直接或間接透過失配邊走到$u$囉～

這些資訊可以利用$queue$先進行預處理，我們得到一個儲存答案的陣列$count$

於是在$B$進行轉移時，我們每走一步，就將目前找到的最長屬於$A$子字串的後綴$S$，沿著失配邊枚舉$S$的後綴集合，然後把它們在$A$中出現的次數全部加進答案裡面
實作上可以將沿著失配邊走的路徑上的每個節點的$count$乘上一個權重，再加起來
權重就是這個節點代表的字串集合中有幾個長度$\geq K$且$\leq \left|S\right|$，透過$len$和每個節點的$max\_len$資訊可以$O(1)$計算出來

這篇先講到這裡，並給出實現目前算法的code
下一篇說明怎麼讓時間複雜度再降低

時間複雜度：$O(\left|A\right|+\left|A\right|\left|B\right|)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int CHARSET=52;
typedef long long LL;
struct SuffixAutomaton
{
    vector<int>EDGE[CHARSET],GREEN,MAX_LEN,COUNT;
    int N;
    void Clear()
    {
        for(int i=0;i<CHARSET;i++)EDGE[i].clear();
        GREEN.clear(),MAX_LEN.clear();
        COUNT.clear();
        N=0;
        NewNode(0);
    }
    void NewNode(const int max_len)
    {
        for(int i=0;i<CHARSET;i++)EDGE[i].push_back(0);
        GREEN.push_back(-1),MAX_LEN.push_back(max_len);
        COUNT.push_back(0);
        N++;
    }
    void Extend(int &last,const int c)
    {
        int cur=last;NewNode(MAX_LEN[last]+1);last=N-1;
        for(;cur!=-1&&!EDGE[c][cur];cur=GREEN[cur])EDGE[c][cur]=last;
        if(cur==-1)GREEN[last]=0;
        else
        {
            const int pg=EDGE[c][cur];
            if(MAX_LEN[pg]==MAX_LEN[cur]+1)GREEN[last]=pg;
            else
            {
                NewNode(MAX_LEN[cur]+1);
                const int wish=N-1;
                for(;cur!=-1&&EDGE[c][cur]==pg;cur=GREEN[cur])EDGE[c][cur]=wish;
                for(int i=0;i<CHARSET;i++)EDGE[i][wish]=EDGE[i][pg];
                GREEN[wish]=GREEN[pg];
                GREEN[pg]=wish;
                GREEN[last]=wish;
            }
        }
        COUNT[last]++;
    }
    int Id(const char a)
    {
        if(a>='a'&&a<='z')return a-'a';
        if(a>='A'&&a<='Z')return a-'A'+26;
        assert(0);return -1;
    }
    void Build(const char *str)
    {
        Clear();
        for(int i=0,u=0;str[i];i++)Extend(u,Id(str[i]));
        queue<int>q;
        int *degree=new int[N];
        for(int i=0;i<N;i++)degree[i]=0;
        for(int i=1;i<N;i++)degree[GREEN[i]]++;
        for(int i=0;i<N;i++)if(!degree[i])q.push(i);
        while(!q.empty())
        {
            const int u=q.front();q.pop();
            if(GREEN[u]!=-1)
            {
                COUNT[GREEN[u]]+=COUNT[u];
                if(!--degree[GREEN[u]])q.push(GREEN[u]);
            }
        }
        for(int i=0;i<N;i++)assert(!degree[i]);
        delete[]degree;
    }
    LL GetCostSum(int cur,const int max_len,const int low_limit)
    {
        if(max_len<low_limit)return 0LL;
        return GetCostSum(GREEN[cur],MAX_LEN[GREEN[cur]],low_limit)+(LL)COUNT[cur]*(max_len-max(MAX_LEN[GREEN[cur]]+1,low_limit)+1);
    }
    LL Match(const char *str,const int low_limit)
    {
        LL ans=0LL;
        for(int i=0,u=0,len=0;str[i];i++)
        {
            const int c=Id(str[i]);
            while(u&&!EDGE[c][u])u=GREEN[u],len=MAX_LEN[u];
            if(EDGE[c][u])u=EDGE[c][u],len++;
            ans+=GetCostSum(u,len,low_limit);
        }
        return ans;
    }
}SAM;
int K;
char A[100001],B[100001];
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&K)==1&&K)
    {
        scanf("%s%s",A,B);
        SAM.Build(A);
        printf("%lld\n",SAM.Match(B,K));
    }
    return 0;
}