轉自我們班大佬的

#include<cstdio>
#include<cstring>
using namespace std;
char s[400005];
int next[400005];
void get_next(int len)
{next[0]=-1;int j=-1;int i=0;while(i<len){if(j==-1||s[len-i-1]==s[len-j-1]) next[++i]= ++j;else j=next[j];}
}
int main()
{int len;while(~scanf("%s",s)){len=strlen(s);get_next(len);int maxcnt=0;int maxl=0;for(int i=1;i<=len;i++){int l=i-next[i];if(l&&i%l==0){int cnt=i/l;if(cnt>=maxcnt){maxcnt=cnt;maxl=l;	}}}if(maxcnt>1){for(int i=len-maxl;i<len;i++) printf("%c",s[i]);printf(" %d\n",maxcnt);}else printf("-1\n");}}

1012: 重復序列

時間限制:?1 Sec??內存限制:?128 MB
提交:?238??解決:?41
[提交][狀態][討論版]

題目描述

為了讓密碼變得更長，fpcsong在密碼的末端增加了一些無意義內容。為了能夠記住密碼，增加的內容往往是重復序列。例如下列密碼

xduacm2015_mimayaochangchangchang

的末端有一重復序列，即"chang"重復3次。現在，給你一個串s，請你確定一個串p和數x，使得p非空，x>1，px（指串p重復x次）為s的后綴。若有多個可能的解，輸出x最大的解。若仍有多解，輸出|p|（p的長度）最大的解。若無解，輸出-1。

輸入

多組數據，每組數據1行，包含一個串s。s中只有字母（大小寫敏感），數字，下劃線。|s|<=400000。

輸出

對于每組數據，輸出1行，若有解輸出串p和整數x，用空格分割。若無解輸出-1。

樣例輸入

xduacm2015_mimayaochangchangchang
orzorzorzorz
Orzorzorzorz
orzorz_diaodiaodiaodiao
we_orz_tencent_light_light
ooooooooooops

樣例輸出

chang 3
orz 4
orz 3
diao 4
_light 2
-1

提示

來源

總結

以上是生活随笔為你收集整理的xdoj 1012的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。