循环小数

时间限制：

3000 ms  |  内存限制：65535 KB

难度：

1

 

描述

我们可爱的 c小加 近段儿正在潜心研究数学，当他学习到循环小数这一部分时不是太明白循环体是什么意思（比如说3.23232323的循环体是23、2323、23232323），假设我们现在的循环小数都是严格循环的并且有限的，也就是说不出现2.16666666（循环体为6，长度为1）的情况，只有123123这样的循环出现。给他一个小数，他需要找出最小循环体的长度、循环体和循环的次数，请你帮他解决这个问题。

 

输入

输入的第一行是t，表示有t组测试数据（t<=100）。

随后的t行，每行都是一个小于10并且大于0的小数（总长度<=200）。

输出

对每组输入，输出结果单独成行，输出最小循环体的长度、循环体和出现循环的次数。

样例输入

38.69876987698769870.6665.1

样例输出

4 6987 41 6 31 1 1

来源

上传者

做了这么多Kmp, 还是思路不清晰。

ac:

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 using namespace std; 5 char a[220], b[220]; int p[220], lena, k; 6 void Getp() 7 { 8     int i = 0, j = -1; 9     p[i] = j;10     while(i < k)11     {12         if(j == -1 || b[i] == b[j])13         {14             i++; j++;15             p[i] = j;16         }17         else18             j = p[j];19     }20 }21 int main()22 {23     int t;24     scanf("%d", &t);25     while(t--)26     {27         int i;28         scanf("%s", a);29         lena = strlen(a);    30         for(i = 0; i < lena; i++)31         {32             if(a[i] == '.')33             {34                 i += 1;35                 break;36             }37         }38     //    printf("%d\n", i);39         k = 0;40         for(; i < lena; i++)41             b[k++] = a[i];42     //        printf("%d\n", k);43         Getp();44         printf("%d ", k - p[k]);45         for(i = 0; i < k - p[k]; i++)46             printf("%c", b[i]);47         printf(" ");48         printf("%d\n", k/(k-p[k])); 49     }50     return 0;51 }