POJ-Common Substrings(后缀数组-长度不小于 k 的公共子串的个数)-白红宇

POJ-Common Substrings(后缀数组-长度不小于 k 的公共子串的个数)

阅读量：5280 次

发布时间：2019-06-14

本文共 2600 字，大约阅读时间需要 8 分钟。

题意：

长度不小于 k 的公共子串的个数

分析：

基本思路是计算 A 的所有后缀和 B 的所有后缀之间的最长公共前缀的长度,把最长公共前缀长度不小于 k 的部分全部加起来。

先将两个字符串连起来,中间用一个没有出现过的字符隔开。按 height 值分组后,接下来的工作便是快速的统计每组中后缀之间的最长公共前缀之和。

扫描一遍,每遇到一个 B 的后缀就统计与前面的 A 的后缀能产生多少个长度不小于 k 的公共子串,

这里 A 的后缀需要用一个单调的栈来高效的维护。然后对 A 也这样做一次。

// File Name: 3415.cpp// Author: Zlbing// Created Time: 2013年09月07日 星期六 14时58分18秒#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define CL(x,v); memset(x,v,sizeof(x));#define INF 0x3f3f3f3f#define LL long long#define REP(i,r,n) for(int i=r;i<=n;i++)#define RREP(i,n,r) for(int i=n;i>=r;i--)//rank从0开始//sa从1开始,因为最后一个字符(最小的)排在第0位//height从2开始,因为表示的是sa[i-1]和sa[i]const int MAXN=220000;int rank[MAXN],sa[MAXN],X[MAXN],Y[MAXN],height[MAXN];char s[MAXN];int buc[MAXN];void calheight(int n) { int i , j , k = 0; for(i = 1 ; i <= n ; i++) rank[sa[i]] = i; for(i = 0 ; i < n ; height[rank[i++]] = k) for(k?k--:0 , j = sa[rank[i]-1] ; s[i+k] == s[j+k] ; k++);}bool cmp(int *r,int a,int b,int l) { return (r[a] == r[b] && r[a+l] == r[b+l]);}void suffix(int n,int m = 128) { int i , l , p , *x = X , *y = Y; for(i = 0 ; i < m ; i ++) buc[i] = 0; for(i = 0 ; i < n ; i ++) buc[ x[i] = s[i] ] ++; for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[i] ]] = i; for(l = 1,p = 1 ; p < n ; m = p , l *= 2) { p = 0; for(i = n-l ; i < n ; i ++) y[p++] = i; for(i = 0 ; i < n ; i ++) if(sa[i] >= l) y[p++] = sa[i] - l; for(i = 0 ; i < m ; i ++) buc[i] = 0; for(i = 0 ; i < n ; i ++) buc[ x[y[i]] ] ++; for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[y[i]] ] ] = y[i]; for(swap(x,y) , x[sa[0]] = 0 , i = 1 , p = 1 ; i < n ; i ++) x[ sa[i] ] = cmp(y,sa[i-1],sa[i],l) ? p-1 : p++; } calheight(n-1);//后缀数组关键是求出height,所以求sa的时候顺便把rank和height求出来}char ch[MAXN];LL h[MAXN],w[MAXN];//单调栈h中每个元素如h[j]代表一个区间，这个区间内每一个后缀与当前位置i的LCP都为h[j]//w[j]表示与但前位置i的LCP为h[j]的个数LL num[MAXN];int top;int main() { int k; while(~scanf("%d",&k)) { if(!k)break; scanf("%s",s); scanf("%s",ch); int len1=strlen(s); int len2=strlen(ch); s[len1]=1; for(int i=len1+1;i
                 
                  =height[i];top--) { cnt+=w[top]; } h[++top]=height[i]; //当sa[i-1]为B的后缀时，加1 w[top]=cnt+(sa[i-1]>len1); num[top]=num[top-1]+h[top]*w[top]; //sa[i]为A的后缀时，统计与前面B的后缀产生的公共子串 if(sa[i]
                  
                   =height[i];top--) { cnt+=w[top]; } h[++top]=height[i]; w[top]=cnt+(sa[i-1]
                   
                    len1) { ans+=num[top]; } } } printf("%lld\n",ans); } return 0;}

转载于:https://www.cnblogs.com/arbitrary/p/3308423.html

你可能感兴趣的文章