首页 > 代码库 > 后缀数组四·重复旋律4
后缀数组四·重复旋律4
后缀数组四·重复旋律4
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为(k,l)-重复的，如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的，因为它由aba重复4次组成。
小Hi想知道一部作品中k最大的(k,l)-重复旋律。
解题方法提示
输入
一行一个仅包含小写字母的字符串。字符串长度不超过 100000。
输出
一行一个整数，表示答案k。
- 样例输入
babbabaabaabaabab
- 样例输出
4
分析：后缀数组+二分；
枚举长度l，计算到lcp（i，i+l）（（i-1）%l==0），
在判断lcp（i-1，i+l-1），lcp（i-2，i+l-2）...lcp（i-l+1，i+1）时，
只需判断lcp（i-l+lcp（i，i+l），i+lcp（i，i+l））是否变大即可；
代码：#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <unordered_map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, ls[rt]#define Rson mid+1, R, rs[rt]#define sys system("pause")#define freopen freopen("in.txt","r",stdin)const int maxn=1e5+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){ ll x=0;int f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int n,m,k,t,cntA[maxn],cntB[maxn],sa[maxn],lev[maxn],height[maxn],A[maxn],B[maxn],tsa[maxn],st[20][maxn],p[maxn],ans;char ch[maxn];void init(){ for(int i=2;i<=n;i++)p[i]=1+p[i>>1]; for(int i=1;i<=n;i++)st[0][i]=height[i]; for(int i=1;i<=19;i++) for(int j=1;j+(1LL<<i)-1<=n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);}int lcp(int a,int b){ a=lev[a],b=lev[b]; if(a>b)swap(a,b); a++; int x=p[b-a+1]; return min(st[x][a],st[x][b-(1<<x)+1]);}void solve(){ for (int i = 0; i < 128; i ++) cntA[i] = 0; for (int i = 1; i <= n; i ++) cntA[ch[i]] ++; for (int i = 1; i < 128; i ++) cntA[i] += cntA[i - 1]; for (int i = n; i; i --) sa[cntA[ch[i]] --] = i; lev[sa[1]] = 1; for (int i = 2; i <= n; i ++) { lev[sa[i]] = lev[sa[i - 1]]; if (ch[sa[i]] != ch[sa[i - 1]]) lev[sa[i]] ++; } for (int l = 1; lev[sa[n]] < n; l <<= 1) { for (int i = 0; i <= n; i ++) cntA[i] = 0; for (int i = 0; i <= n; i ++) cntB[i] = 0; for (int i = 1; i <= n; i ++) { cntA[A[i] = lev[i]] ++; cntB[B[i] = (i + l <= n) ? lev[i + l] : 0] ++; } for (int i = 1; i <= n; i ++) cntB[i] += cntB[i - 1]; for (int i = n; i; i --) tsa[cntB[B[i]] --] = i; for (int i = 1; i <= n; i ++) cntA[i] += cntA[i - 1]; for (int i = n; i; i --) sa[cntA[A[tsa[i]]] --] = tsa[i]; lev[sa[1]] = 1; for (int i = 2; i <= n; i ++) { lev[sa[i]] = lev[sa[i - 1]]; if (A[sa[i]] != A[sa[i - 1]] || B[sa[i]] != B[sa[i - 1]]) lev[sa[i]] ++; } } for (int i = 1, j = 0; i <= n; i ++) { if (j) j --; while (ch[i + j] == ch[sa[lev[i] - 1] + j]) j ++; height[lev[i]] = j; }}int main(){ int i,j; scanf("%s",ch+1); n=strlen(ch+1); solve(); init(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j+=i) { int x=lcp(j,j+i); ans=max(ans,x/i+1); if(j-i+x%i>0) { ans=max(ans,lcp(j-i+x%i,j+x%i)/i+1); } } } printf("%d\n",ans); //system("Pause"); return 0;}
后缀数组四·重复旋律4
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。