POJ 3415 Common Substrings【后缀自动机】

拼搏现实的明天。 2022-08-08 14:56 111阅读 0赞

max：即代码中 len 变量，它表示该状态能够接受的最长的字符串长度。  
min：表示该状态能够接受的最短的字符串长度。实际上等于该状态的 fail 指针指向的结点的 len + 1。  
max-min+1：表示该状态能够接受的不同的字符串数。  
right：表示节点u所能够接受的字符，在原字符串中出现过多少次  
right\*(max-min+1)就是节点u能够接受的字符串在原字符串中出现的次数。

那么现在有了最小的限制K，所以min变成了max(min,K)。  
我们这样做，先给第一个串建好sam，然后用第二个串去sam上匹配，匹配过程中，记录temp，表示s2匹配到当前位置时，能匹配的最大长度，假设此时匹配到sam上的位置是p。  
这时，我们可以得到的长度大于等于K的，在s2中以当前位置结束的公共子串的个数，为`(cnt-max(K,len[fa[now]]+1)+1)`  
这样的串在s1中会出现在哪些位置呢？那就是p的right集合了。所以我们先处理出每个节点的right集合的大小.那么s2\[i\]这个位置，与s1的p状态能匹配的大于等于K的公共子串的个数就是 `(cnt-max(K,len[fa[now]]+1)+1)*right[now]`了。  
如果`len[fa[now]]>=K`， 那么我们必然还可以从父亲那里匹配出若干个符合要求的子串，而且不管是从哪个儿子过来的，fa处能增加的个数都是一样的。因此我们像线段树延迟标记那样，给父亲节点打上一个标记，当s2枚举完了之后，在根据拓扑序，将延迟标记dp往上推就好了。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=100010;
    const int MAC=55;
    
    struct SAM
    {
        int len[MAXN<<1],next[MAXN<<1][MAC],fa[MAXN<<1],L,last;
        ll right[MAXN<<1],dp[MAXN<<1];
        SAM()
        {
            init();
        }
        void init()
        {
            L=0;
            last=newnode(0,-1);
        }
        int idx(char ch)
        {
            if(ch>='a' && ch<='z')  return ch-'a';
            return ch-'A'+26;
        }
        int newnode(int l,int pre)
        {
            fa[L]=pre;
            right[L]=0;dp[L]=0;
            for(int i=0; i<MAC; i++)    next[L][i]=-1;
            len[L]=l;
            return L++;
        }
        void build(char *p,int K)
        {
            int le=strlen(p);
            for(int i=0; i<le; i++)
                add(idx(p[i]),i);
            toposort();
            for(int i=L-1;i>=0;i--)
            {
                int u=topo[i];
                if(~fa[u])
                    right[fa[u]]+=right[u];
            }
        }
        void add(int x,int l)
        {
            int pre=last,now=newnode(len[pre]+1,-1);
            last=now;right[last]++;
            while(~pre&&next[pre][x]==-1)
            {
                next[pre][x]=now;
                pre=fa[pre];
            }
            if(pre==-1) fa[now]=0;
            else
            {
                int bro=next[pre][x];
                if(len[bro]==len[pre]+1)    fa[now]=bro;
                else
                {
                    int fail=newnode(len[pre]+1,fa[bro]);
                    for(int i=0; i<MAC; i++)
                    {
                        next[fail][i]=next[bro][i];
                    }
                    fa[bro]=fa[now]=fail;
                    while(~pre&&next[pre][x]==bro)
                    {
                        next[pre][x]=fail;
                        pre=fa[pre];
                    }
                }
            }
        }
        int sum[MAXN<<1],topo[MAXN<<1];
        void toposort()
        {
            CLR(sum,0);
            for(int i=0; i<L; i++)    sum[len[i]]++;
            for(int i=1; i<L; i++)    sum[i]+=sum[i-1];
            for(int i=0; i<L; i++)    topo[--sum[len[i]]]=i;
        }
    
    
        ll find(char *s,int K)
        {
            ll ans=0,now=0,cnt=0;
            int n=strlen(s);
            for(int i=0; i<n; i++)
            {
                int x=idx(s[i]);
                if(~next[now][x])
                {
                    cnt++;
                    now=next[now][x];
                }
                else
                {
                    while(~now && next[now][x]==-1)
                        now=fa[now];
    
                    if(now==-1)
                        cnt=0,now=0;
                    else
                    {
                        cnt=len[now]+1;
                        now=next[now][x];
                    }
                }
                if(cnt>=K)
                {
                    if(~fa[now])
                    {
                        ans+=(cnt-max(K,len[fa[now]]+1)+1)*right[now];
                            if(len[fa[now]]>=K)
                                dp[fa[now]]++;
                    }
                }
            }
            for(int i=L-1;i>=0;i--)
            {
                int u=topo[i];
                if(dp[u])
                {
                    if(~fa[u])
                    {
                        ans+=dp[u]*(len[u]-max(K,len[fa[u]]+1)+1)*right[u];
                        if(len[fa[u]]>=K)
                            dp[fa[u]]+=dp[u];
                    }
                }
            }
            //cout<<endl;
            return ans;
        }
    } T;
    char str[MAXN];
    
    int main()
    {
        int K;
        while(read(K)&&K)
        {
            scanf("%s",str);
            T.init();
            T.build(str,K);
            scanf("%s",str);
            printf("%lld\n",T.find(str,K));
        }
    }