题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1358

题目大意:给你一串字符串,判断字符串的前缀是否由某些字符串多次重复而构成。

也就是,从第1个字母到第2字母组成的字符串可由某一周期性的字串(“a”)

的两次组成,也就是aa有两个a组成;

第三行自然就是aabaab可有两个aab组成;

第四行aabaabaab可由三个aab组成;

第五行aabaabaabaab可由四个aab组成。

解题思路:同HDU 3746类似,通过计算字符串前缀的循环节获得相应周期即可。

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+; int m;
int nxt[N];
char p[N]; void getnext(){
int i,j;
i=,j=nxt[]=-;
while(i<m){
while(j!=-&&p[i]!=p[j])
j=nxt[j];
nxt[++i]=++j;
}
} int main(){
int cas=;
while(scanf("%d",&m)&&m){
scanf("%s",p);
getnext();
printf("Test case #%d\n",++cas);
//枚举长度为2~m的字符串前缀
for(int i=;i<=m;i++){
int mmin=i-nxt[i]; //len-nxt[len]为最小循环节
if(i!=mmin&&i%mmin==)
printf("%d %d\n",i,i/mmin);
}
printf("\n");
}
return ;
}
05-06 11:09
查看更多