循环小数
时间限制：3000 ms | 内存限制：65535 KB
难度：1
- 描述
-
我们可爱的 c小加 近段儿正在潜心研究数学，当他学习到循环小数这一部分时不是太明白循环体是什么意思（比如说3.23232323的循环体是23、2323、23232323），假设我们现在的循环小数都是严格循环的并且有限的，也就是说不出现2.16666666（循环体为6，长度为1）的情况，只有123123这样的循环出现。给他一个小数，他需要找出最小循环体的长度、循环体和循环的次数，请你帮他解决这个问题。
- 输入
- 输入的第一行是t，表示有t组测试数据（t<=100）。
随后的t行，每行都是一个小于10并且大于0的小数（总长度<=200）。 - 输出
- 对每组输入，输出结果单独成行，输出最小循环体的长度、循环体和出现循环的次数。
- 样例输入
-
3
8.6987698769876987
0.666
5.1 - 样例输出
-
4 6987 4
1 6 3
1 1 1 看算法看的头疼，水一道#include<stdio.h>
#include<string.h>
int f[210];
int len,len1;
char str[210],s[210];
char put[210];
void getmap()
{
int i,j,k;
memset(s,'\0',sizeof(s));
scanf("%s",str);
len=strlen(str);
for(i=0;i<len;i++)
{
if(str[i]=='.')
{
k=i;
break;
}
}
j=0;
for(i=k+1;i<len;i++)
s[j++]=str[i];
len1=strlen(s);
}
void getfail()
{
int i,j;
f[0]=f[1]=0;
for(i=1;i<len1;i++)
{
j=f[i];
while(j&&s[i]!=s[j])
j=f[j];
f[i+1]=s[i]==s[j]?j+1:0;
}
}
void kmp()
{
int i,j,length,times;
int k;
length=len1-f[len1];
times=len1/(len1-f[len1]);
j=0;
for(i=0;i<len1;i++)
{
while(j&&s[i]!=s[j])
j=f[j];
if(s[i]==s[j])
j++;
if(j==length)
{
k=i-length+1;//循环体出现位置
break;
}
}
memset(put,'\0',sizeof(put));
j=0;
for(i=k;i<length;i++)
put[j++]=s[i];
printf("%d %s %d\n",length,put,times);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
getmap();
getfail();
kmp();
}
return 0;
}