大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
随着扩展KMP做一个简单的努力…..
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=100100; char T[maxn],P[maxn]; int next[maxn],ex[maxn]; void pre_exkmp(char P[]) { int m=strlen(P); next[0]=m; int j=0,k=1; while(j+1<m&&P[j]==P[j+1]) j++; next[1]=j; for(int i=2;i<m;i++) { int p=next[k]+k-1; int L=next[i-k]; if(i+L<p+1) next[i]=L; else { j=max(0,p-i+1); while(i+j<m&&P[i+j]==P[j]) j++; next[i]=j; k=i; } } } void exkmp(char P[],char T[]) { int m=strlen(P),n=strlen(T); pre_exkmp(P); int j=0,k=0; while(j<n&&j<m&&P[j]==T[j]) j++; ex[0]=j; for(int i=1;i<n;i++) { int p=ex[k]+k-1; int L=next[i-k]; if(i+L<p+1) ex[i]=L; else { j=max(0,p-i+1); while(i+j<n&&j<m&&T[i+j]==P[j]) j++; ex[i]=j; k=i; } } } int pos[maxn],sum[maxn],mx=-1; struct ANS { int a,b; }ans[maxn]; int na=0; bool cmp(ANS x,ANS y) { if(x.a!=y.a)return x.a<y.a; return x.b<y.b; } int lisan[maxn],nl; int main() { cin>>P; pre_exkmp(P); int n=strlen(P); for(int i=0;i<n;i++) { pos[next[i]]++; lisan[nl++]=next[i]; mx=max(mx,next[i]); } sort(lisan,lisan+nl); int t=unique(lisan,lisan+nl)-lisan; for(int i=t-1;i>=0;i--) { sum[lisan[i]]=sum[lisan[i+1]]+pos[lisan[i]]; } for(int i=0;i<n;i++) { if(next[i]==n-i) { ans[na++]=(ANS){next[i],sum[next[i]]}; } } sort(ans,ans+na,cmp); printf("%d\n",na); for(int i=0;i<na;i++) { printf("%d %d\n",ans[i].a,ans[i].b); } return 0; }
版权声明:来自: 代码代码猿猿AC路 http://blog.csdn.net/ck_boss
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116863.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...