51nod 1732 51nod婚姻介绍所 后缀数组：最长公共前缀

本文主要是介绍51nod 1732 51nod婚姻介绍所 后缀数组：最长公共前缀，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1732 51nod婚姻介绍所

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 40 分
6.  
7. 4级题

51nod除了在做OJ之外，还开展了很多副业。婚姻介绍所就是其中之一。

对于一个客户，我们可以使用一个字符串来描述该客户的特质。

假设现在我们有两个客户A和B。

A的特质字符串为：abcdefg

B的特质字符串为：abcxyz

则A和B的匹配度f(A, B)为A和B的最长公共前缀的长度，即len('abc') = 3

由于最近51nod经费紧张，所以夹克大老爷设计了一种压缩算法以节约内存。

所有用户的特质字符串都被存储在了一个长为n的字符串S中。(n <= 1000)用户的特质使用一个整数p表示，表示该用户的特质字符串为S[p...n - 1]。

现给定字符串S，与q次查询<ai, bi>（ai, bi分别为合法的用户特质整数）。请输出q次查询分别对应的客户匹配度。

 

 收起

输入

现给定字符串长度n，与字符串S。接下来是整数q，代表接下来有q次查询。
下面q行有两个整数ai, bi。代表查询特质为ai与bi的用户的匹配度。1 <= n <= 1000
1 <= q <= 10^6输入数据全部合法。

输出

每一行输出一个用户匹配度整数。

输入样例

12
loveornolove
5
3 7
0 0
9 1
3 1
9 5

输出样例

0
12
3
0
0

 

分析：

后缀数组的模板题，注意快读

#include <bits/stdc++.h>
using namespace std;
const int maxn=200000+1000;
int len1,len2;
void in(int &x)
{x=0;char c=getchar();while(c<'0'||c>'9'){c=getchar();}x=c-'0';while(c=getchar()){if(c<'0'||c>'9') break;x=x*10+c-'0';}
}void out(int x)
{if(x>=10)out(x/10);putchar(x%10+'0');
}
struct SuffixArray
{char s[maxn];///_rank[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCPint sa[maxn],_rank[maxn],height[maxn];///c[i] 基数排序辅助数组int t1[maxn],t2[maxn],c[maxn],n;int dmin[maxn][21];void init(){memset(height,0,sizeof(height));memset(_rank,0,sizeof(_rank));memset(sa,0,sizeof(sa));memset(c,0,sizeof(c));memset(t1,0,sizeof(t1));memset(t2,0,sizeof(t2));memset(dmin,0,sizeof(dmin));}void build_sa(int m)  ///m大于s[]数组出现的任意字符的int值{/// x[i]是第i个元素的第一关键字  y[i]表示第二关键字排名为i的数，第一关键字的位置int i,p,*x=t1,*y=t2;x[n]=y[n]=-1;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(int k=1; k<=n; k<<=1){p=0;for(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[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);p=1;x[sa[0]]=0;for(i=1; i<n; i++){if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=p-1;elsex[sa[i]]=p++;}if(p>=n)break;m=p;}}void build_height()//单个字符也行{int i,j,k=0,r;for(i=0; i<n; i++)_rank[sa[i]]=i;height[0]=0;for(i=0; i<n; i++){if(k)k--;r=_rank[i];if(r==0)continue;j=sa[r-1];while(s[i+k]==s[j+k])k++;height[_rank[i]]=k;}}int LongestMessage() //最长公共子串{int ans=0;for(int i=2; i<n; i++){int a1=sa[i-1],a2=sa[i];if(a1>a2)swap(a1,a2);if(a1>=0&&a1<=len1-1&&a2>=len1+1&&a2<=len1+len2)ans = max(ans,height[i]);}return ans;}void initMin(){for(int i=0; i<n; i++)dmin[i][0]=height[i];for(int j=1; (1<<j)<=n; j++)for(int i=0; i+(1<<j)-1<n; i++)dmin[i][j]=min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);}int RMQ(int L,int R)//取得范围最小值{int k=0;while((1<<(k+1))<=R-L+1)k++;return min(dmin[L][k], dmin[R-(1<<k)+1][k]);}int LCP(int i,int j)//求后缀i和j的LCP最长公共前缀{if(i==j) return n-i;int L=_rank[i],R=_rank[j];//求后缀i与后缀j的LCP//if(i==j) return n-sa[i];//int L=i,R=j;//直接求排名i与j后缀的LCPif(L>R)swap(L,R);L++;//注意这里return RMQ(L,R);}int num()//子串的个数{int ans=0;for(int i=1; i<n; i++)ans += n-1-sa[i]-height[i];return ans;}//确定子串[be,be+len-1]的在后缀排名区间[L,R]int get_LR(int be,int len,int &L,int &R){int pos=_rank[be];int l=0,r=pos;while(l<r){int mid=(l+r)>>1;if(RMQ(mid+1,pos)>=len)r=mid;elsel=mid+1;}L=l;l=pos;r=n-1;while(l<r){int mid=(l+r+1)>>1;if(RMQ(pos+1,mid)>=len)l=mid;elser=mid-1;}R=l;}//恰好出现w次子串的个数int num_w(int w){int ans=0;for(int i=0; i+w-1<n; i++)ans+=max(0,LCP(i,i+w-1)-max(height[i],height[i+w]));return ans;}void out(){for(int i=0; i<n; i++){cout<<sa[i]<<" ";}cout<<endl;for(int i=0; i<n; i++){cout<<_rank[i]<<" ";}cout<<endl;for(int i=0; i<n; i++){cout<<height[i]<<" ";}cout<<endl;}
} sa;
int main()
{sa.init();scanf("%d",&len1);scanf("%s",sa.s);sa.n=len1;sa.build_sa(256);sa.build_height();sa.initMin();int q;in(q);int a,b;while(q--){in(a);in(b);if(a==b)out(len1-a);elseout(sa.LCP(a,b));puts("");}return 0;
}

 

 

这篇关于51nod 1732 51nod婚姻介绍所 后缀数组：最长公共前缀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---