POJ 3415-Common Substrings（后缀数组+单调栈-公共子串的长度）

淡淡的烟草味﹌ 2022-06-17 09:16 171阅读 0赞

Common Substrings

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;10850</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3587</td> 
  </tr> 
 </tbody> 
</table>

Description

A substring of a string *T* is defined as:

*T*( *i*, *k*)= *TiTi* \+1... *Ti+k* \-1, 1≤ *i*≤ *i+k*\-1≤| *T*|.

Given two strings *A*, *B* and one integer *K*, we define *S*, a set of triples (*i*, *j*, *k*):

*S* = \{( *i*, *j*, *k*) | *k*≥ *K*, *A*( *i*, *k*)= *B*( *j*, *k*)\}.

You are to give the value of |*S*| for specific *A*, *B* and *K*.

Input

The input file contains several blocks of data. For each block, the first line contains one integer *K*, followed by two lines containing strings *A* and *B*, respectively. The input file is ended by *K*=0.

1 ≤ |*A*|, |*B*| ≤ 105  
1 ≤ *K* ≤ *min*\{|*A*|, |*B*|\}  
Characters of *A* and *B* are all Latin letters.

Output

For each case, output an integer |*S*|.

Sample Input

2
    aababaa
    abaabaa
    1
    xx
    xx
    0

Sample Output

22
    5

Source

[POJ Monthly--2007.10.06][], wintokk

## 题目意思： ##

给出两个字符串，计算它们所有的长度大于K的公共子串的个数（可以重复）。

## 解题思路： ##

只想到用后缀数组，妥妥会TLE，看了一下大神说加单调栈优化，单调栈的思路不难，看的时候就是不明白如何用它来优化…(\*゜ー゜\*)

按照之前求最长公共子串长度的题目，两串加‘$’连接后求得高度数组，然后分B去匹配A、A去匹配B两种情况来扫描，其实思路是一样的，所以举一个B去匹配A栗子来说明。

『

\_( ﾟДﾟ)ﾉ首先必须要满足的条件是①最长公共子串长度大于K；②分属于两个不同字符串即A串和B串。

当A的后缀与B的后缀的最长公共前缀长度（最长公共子串长度）大于K，且当前是A串的位置时，个数+=高度数组lcp\[i\]-长度限制K+1，因为长度范围在\[K, \]均满足题意，区间内个数是lcp\[i\]-K+1。

单调栈维护一个栈顶是不小于K的最小公共前缀长度的高度数组及其对应个数的序列，每次如果当前最小公共前缀长度小于栈顶元素则需要调整：去掉出栈元素多加了的个数、满足条件的A后缀串的个数加上出栈元素对应的个数。

因为现在栈顶元素变的更小了，所以更小的元素肯定是包含了之前那个比它大的元素对应的“公共子串的个数”，我们就要在调整的过程中减去这部分被重复计算的元素个数。

最后需要再次判断相邻后缀是否属于B串，此时满足分属于两个不同字符串，即A串和B串。

』

同理对A去匹配B再次扫描，区别是先判断属于B串再判断属于A串来判定分属于两个不同字符串，将两次扫描的结果相加。

Note：小心地参考了若干大神的博客以及传遍大江南北的后缀数组论文。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    #define MAXN 200100
    int n,k,m,lens;
    long long ans=0;
    string s,t;
    int sa[MAXN],lcp[MAXN];
    int rank[MAXN*2],tmp[MAXN*2];
    void construct_lcp(string s,int sa[],int lcp[])
    {
        int n=s.length();
        for(int i=0; i<=n; ++i)
            rank[sa[i]]=i;
        int h=0;
        lcp[0]=0;
        for(int i=0; i<n; ++i)
        {
            int j=sa[rank[i]-1];
            if(h>0) --h;
            for(; j+h<n&&i+h<n; ++h)
                if(s[j+h]!=s[i+h]) break;
            lcp[rank[i]-1]=h;
        }
    }
    bool compare_sa(int i,int j)//倍增法,比较rank
    {
        if(rank[i]!=rank[j]) return rank[i]<rank[j];
        else
        {
            int ri=i+k<=n?rank[i+k] :-1;
            int rj=j+k<=n?rank[j+k] :-1;
            return ri<rj;
        }
    }
    
    void construct_sa(string s,int sa[])//计算s的后缀数组
    {
        for(int i=0; i<=n; ++i)//初始长度为1，rank为字符编码
        {
            sa[i]=i;
            rank[i]=i<n?s[i] :-1;
        }
        for(k=1; k<=n; k*=2)//倍增法求后缀数组
        {
            sort(sa,sa+n+1,compare_sa);
            tmp[sa[0]]=0;
            for(int i=1; i<=n; ++i)
                tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
            for(int i=0; i<=n; ++i)
                rank[i]=tmp[i];
        }
    }
    bool contain(string s,int sa[],string t)
    {
        int a=0,b=s.length();
        while(b-a>1)
        {
            int c=(a+b)/2;
            if(s.compare(sa[c],t.length(),t)<0) a=c;
            else b=c;
        }
        return s.compare(sa[b],t.length(),t)==0;
    }
    void solve()
    {
        int dull[MAXN][2];//维护后缀的单调递减栈,栈顶最小,dull[i][0]是lcp[i],dull[i][1]是个数
        long long temp,top;//temp记录当前栈中所有项和一个刚进入的子串匹配所能得到的总的子串的数目
        ans=0;
        //第一次扫描，B串中的子串匹配rank比其高的A子串
        for(int i=0; i<n; i++) //每遇到一个B的后缀就统计与前面的A的后缀能产生多少个长度不小于k的公共子串
        {
            if (lcp[i]<m) top=temp=0;
            else//A的后缀与B的后缀的最长公共前缀长度满足限制条件
            {
                int res=0;//满足条件的A后缀串的个数
                if(sa[i]<lens)//在第一个串中
                {
                    ++res;
                    temp+=lcp[i]-m+1;//更新个数,长度范围在[m,最长公共前缀长度]均满足题意
                }
                while(top>0&&lcp[i]<=dull[top-1][0])//调整单调栈,当前最长公共前缀长度比栈顶元素还小
                {
                    --top;
                    temp-=dull[top][1]*(dull[top][0]-lcp[i]);//去掉出栈元素多加了的个数
                    res+=dull[top][1];
                }
                dull[top][0]=lcp[i];
                dull[top++][1]=res;
                if(sa[i+1]>lens)//在第二个串中，即分属于两个不同字符串
                    ans+=temp;
            }
        }
        //第二次扫描，A串中的子串匹配rank比其高的B子串
        for(int i=0; i<n; i++)
        {
            if (lcp[i]<m) top=temp=0;
            else
            {
                int res=0;//满足条件的B后缀串的个数
                if(sa[i]>lens)//在第二个串中
                {
                    ++res;
                    temp+=lcp[i]-m+1;
                }
                while (top>0&&lcp[i]<=dull[top-1][0])
                {
                    --top;
                    temp-=dull[top][1]*(dull[top][0]-lcp[i]);
                    res+=dull[top][1];
                }
                dull[top][0]=lcp[i];
                dull[top++][1]=res;
                if(sa[i+1]<lens)//在第一个串中，即分属于两个不同字符串
                    ans+=temp;
            }
        }
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        while(cin>>m)
        {
            if(m==0) break;
            cin>>s;
            cin>>t;
            lens=s.length();
            s+='$'+t;//连接串
            n=s.length();
            construct_sa(s,sa);
            construct_lcp(s,sa,lcp);
            solve();
            cout<<ans<<endl;
        }
        return 0;
    }

[POJ Monthly--2007.10.06]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2007.10.06