首页 > 代码库 > URAL 1297 后缀数组:求最长回文子串
URAL 1297 后缀数组:求最长回文子串
思路:这题下午搞了然后一直WA,后面就看了Discuss,里面有个数组:ABCDEFDCBA,这个我输出ABCD,所以错了。
然后才知道自己写的后缀数组对这个回文子串有bug,然后就不知道怎么改了。
然后看题解,里面都是用RMQ先预处理任意两个后缀的最长公共前缀,因为不太知道这个,所以又看了一下午,嘛嘛……
然后理解RMQ和后缀一起用的时候才发现其实这里不用RMQ也可以,只要特殊处理一下上面这个没过的例子就行了,哈哈……机智……
不过那个国家集训队论文里面正解是用RMQ做的,自己还得会和RMQ一起使用才得,在别的题目里面也是要用的。
这个是不用RMQ做的:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<set> #include<cmath> #include<bitset> #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff #define maxn 4010 using namespace std; typedef long long ll; typedef unsigned long long ull; void radix(int *str,int *a,int *b,int n,int m) { static int count[maxn]; mem(count,0); for(int i=0; i<n; i++) ++count[str[a[i]]]; for(int i=1; i<=m; i++) count[i]+=count[i-1]; for(int i=n-1; i>=0; i--) b[--count[str[a[i]]]]=a[i]; } void suffix(int *str,int *sa,int n,int m) { static int rank[maxn],a[maxn],b[maxn]; for(int i=0; i<n; i++) rank[i]=i; radix(str,rank,sa,n,m); rank[sa[0]]=0; for(int i=1; i<n; i++) rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]); for(int i=0; 1<<i<n; i++) { for(int j=0; j<n; j++) { a[j]=rank[j]+1; b[j]=j+(1<<i)>=n?0:rank[j+(1<<i)]+1; sa[j]=j; } radix(b,sa,rank,n,n); radix(a,rank,sa,n,n); rank[sa[0]]=0; for(int j=1; j<n; j++) rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]); } } void calcHeight(int *str,int *sa,int *h,int n) { static int rank[maxn]; int k=0; h[0]=0; for(int i=0; i<n; i++) rank[sa[i]]=i; for(int i=0; i<n; i++) { k=k==0?0:k-1; if(rank[i]) while(str[i+k]==str[sa[rank[i]-1]+k]) k++; else k=0; h[rank[i]]=k; } } int a[maxn],sa[maxn],height[maxn]; int main() { string s; while(cin>>s) { string str; for(int i=s.size()-1; i>=0; i--) str+=s[i]; str=s+"#"+str; copy(str.begin(),str.end(),a); int n=str.size(); suffix(a,sa,n,n+256); calcHeight(a,sa,height,n); int len=0,pos=1; for(int i=1; i<n; i++) if(sa[i]+sa[i-1]==n-height[i]&&((sa[i]<s.size())!=(sa[i-1]<s.size()))) { if(height[i]>len) { len=height[i]; pos=min(sa[i],sa[i-1]); } else if(height[i]==len) pos=min(pos,min(sa[i],sa[i-1])); } if(len>1) cout<<str.substr(pos,len)<<endl; else cout<<s[0]<<endl; } return 0; } /* ABCDDCBAEFDCBA ABCDEFDCBA //要是没有sa[i]+sa[i-1]==n-height[i]这个例子会输出ABCD ABCDDBCA AAAAA AAAA A */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。