信息学奥赛一本通T1466-Power Strings-题解（C语言代码）

解题思路:

求解最多循环子串个数可以等效为求解最小循环子串的长度问题，只需要循环遍历子串长度从1到len/2的区间，若有解则输出len/最小子串长度，若无解则最小循环子串长度为len，最多循环子串个数为1；

注意事项:存储子串的数组区间大小要设置为2000000；

参考代码:

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define MIN(a,b) (a<b?a:b)

int main()

{

     char str[1000001], str1[2000001];

    while (scanf("%s", str) && strcmp(str, ".") != 0)

    {

             int result = 1;

             int a[1000001] = { 0 };

             int len = strlen(str);

             for (int i = 1; i <= len / 2; i++)

                {

                    int dg = 0;

                    if (len%i == 0 && a[i] == 0)

                       {

                             memset(str1, 0, sizeof(char) * 2000001);

                             strncpy(str1, str, i);

                              while (1)

                              {

                                  strncat(str1, str,strlen(str1));

                                  if (strncmp(str1, str, MIN(strlen(str1), len)) != 0)break;

                                  else

                                 {

                                     if (strlen(str1) >= len)

                                       {

                                          dg = i;

                                          break;

                                       }

                                   else  a[strlen(str1)] = 1;

                                 }

                             }

                         }

                    if (dg != 0)

                       {

                          result = len / dg;

                          break;

                       }

               }

              printf("%d\n", result);

     }

}