首页 > 代码库 > POJ 1226 Substrings (后缀数组)
POJ 1226 Substrings (后缀数组)
题目大意:
问的是m个字符串里,都出现过的子串。子串也可以出现在这个串的逆序串中。
思路分析:
居然wa在全5个 “a” 的数据上。
二分的时候下界不能为0。。
思路大致上是把原串和逆序串全部处理出来,放入str中,然后在每个串中间加一个没有出现过的。
此处注意输入不仅仅是字母。
然后跑一遍后缀数组。
然后用标记计数就好了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #define maxn 100005 using namespace std; int str[maxn]; int sa[maxn],t1[maxn],t2[maxn],c[maxn],n; void suffix(int m) { int *x=t1,*y=t2; for(int i=0; i<m; i++)c[i]=0; for(int i=0; i<n; i++)c[x[i]=str[i]]++; for(int i=1; i<m; i++)c[i]+=c[i-1]; for(int i=n-1; i>=0; i--)sa[--c[x[i]]]=i; for(int k=1; k<=n; k<<=1) { int p=0; for(int i=n-k; i<n; i++)y[p++]=i; for(int i=0; i<n; i++)if(sa[i]>=k)y[p++]=sa[i]-k; for(int i=0; i<m; i++)c[i]=0; for(int i=0; i<n; i++)c[x[y[i]]]++; for(int i=0; i<m; i++)c[i]+=c[i-1]; for(int i=n-1; i>=0; i--)sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for(int i=1; i<n; i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++; if(p>=n)break; m=p; } } int rank[maxn],height[maxn]; void getheight() { int k=0; for(int i=0; i<n; i++)rank[sa[i]]=i; for(int i=0; i<n; i++) { if(k)k--; if(!rank[i])continue; int j=sa[rank[i]-1]; while(str[i+k]==str[j+k])k++; height[rank[i]]=k; } } char tmp[105]; bool vis[105]; int dex[maxn]; bool check(int len,int m) { int cnt=m; memset(vis,false,sizeof vis); for(int i=1;i<n;i++) { if(height[i]<len) { if(!cnt)return true; cnt=m; memset(vis,false,sizeof vis); } else { if(!vis[dex[sa[i-1]]]) { cnt--; vis[dex[sa[i-1]]]=true; } if(!vis[dex[sa[i]]]) { cnt--; vis[dex[sa[i]]]=true; } } } return false; } int main() { int T; scanf("%d",&T); while(T--) { n=0; int m; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%s",tmp); int len=strlen(tmp); for(int j=0;j<len;j++) { dex[n]=i; str[n++]=tmp[j]; } dex[n]=i; str[n++]=128+i*2-1; reverse(tmp,tmp+len); for(int j=0;j<len;j++) { dex[n]=i; str[n++]=tmp[j]; } dex[n]=i; str[n++]=128+i*2; } str[n-1]=0; suffix(400); getheight(); int l=1,r=100,ans=0; while(l<=r) { int mid=(l+r)>>1; if(check(mid,m)) ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。