lightoj 1428 Melody Comparison 后缀数组

本文主要是介绍lightoj 1428 Melody Comparison 后缀数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给定一个字符串A和字符串B，求A的不包含B的不同子串个数。

思路：首先把B串接到A串后面中间用一个A、B中均未出现的字符隔开，构成字符串s。求出每个字符对应的height[ i ]、sa[ i ]、rank[ i

。我们开一个rmax数组，rmax[ i ]存的是从A串的第i个字符向右能不形成包含B串的串的最长长度，那么我们必须先知道A串哪些位置

开始能形成B串。假设A串的长度为len，B串长度为len1，那么 B串是从s[len+1]开始的，我们也知道以它开始的后缀的rank,即为

rank[len+1]，那么我们直接从rank值为rank[len+1]+1开始找（因为rank[ len+1]之前的字典序必定小于B，不可能构成B），如果它的

height[ i ] >= len1,那么说明它的前缀必定有B，那么rmax[ i ] = len1-1 。对于没有更新的rmax，我们从后向前扫一边如果rmax[i] == -1.

那么rmax[ i ]=rmax[ i+1] + 1。处理玩rmax,我们对A串重构后缀数组。最后我们按着rank对每个位置的字符算，r=min(rmax[ i ],len-sa[ i ])

l=height[ i ]（因为有height[ i ]个与上一个后缀重复），只要r-l >=0 ans+=r-l。详见代码：

// file name: lightoj1428.cpp //
// author: kereo //
// create time:  2014年08月29日 星期五 17时38分36秒 //
//***********************************//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=100000+100;
const int inf=0x3fffffff;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
int n;
char s[MAXN],s1[MAXN];
int sa[MAXN],t1[MAXN],t2[MAXN],rank[MAXN],height[MAXN],c[MAXN],rmax[MAXN];
int cmp(int *r,int a,int b,int l)
{return r[a] == r[b] && r[a+l] == r[b+l];
}
void build_sa(int m)
{int i,k,p=0;int *x=t1,*y=t2;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[i]=s[i]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;for(k=1;p<n;k<<=1,m=p){for(p=0,i=n-k;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[y[i]]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];swap(x,y);for(p=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],k) ? p-1 : p++;}
}
void calheight(int n)
{int k=0;for(int i=1;i<=n;i++) rank[sa[i]]=i;for(int i=0;i<n;i++){if(k) k--;int j=sa[rank[i]-1];while(s[i+k] == s[j+k]) k++;height[rank[i]]=k;}
}
int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%s%s",s,s1);n=strlen(s); int len=n,len1=strlen(s1);s[n++]=1;for(int i=0;i<len1;i++)s[n++]=s1[i];s[n++]=0;build_sa(200); calheight(n-1);memset(rmax,-1,sizeof(rmax));for(int i=rank[len+1]+1;i<n;i++){if(height[i]<len1)break;elsermax[sa[i]]=len1-1;}for(int i=n-1;i>=0;i--)if(rmax[i]<0)rmax[i]=rmax[i+1]+1; n=len+1; s[n-1]=0;build_sa(200); calheight(n-1);ll ans=0;for(int i=1;i<n;i++){int r=min(rmax[sa[i]],len-sa[i]);int l=height[i];if(r-l>0)ans+=r-l;}printf("Case %d: %lld\n",++kase,ans);}return 0;
}

这篇关于lightoj 1428 Melody Comparison 后缀数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---