题目描述

给你一个字符串，请你判断将此字符串转化成a^n形式的最大的n是多少。
例如：abcd=(abcd)^1，则n=1；
         aaaa=a^4，则n=4；
         ababab=(ab)^3，则n=3。
输入格式

输入包含多组测试数据。每组输入为一个字符串，长度不超过100，其中不包含空格等空白符。当输入为一个“.”时，输入结束。
输出

对于每组输入，输出将此字符串转化成a^n形式的最大的n。
样例输入

abcd
aaaa
ababab
.
样例输出

1
4
3
原文链接：http://zju.

想了好久，初步的思路是将前面一小段的字符串（从第一个字符开始的字符串）不断的循环变量 i 与后面第二个开始的字符串进行比较。但是问题是前面一个字符串不知道从哪里开始结束。而后面的也不知道从哪里开始结束。可能我的思路错了？？还是一些具体的细节没想到？？所以还是来请大侠指点一下核心的思路。最好能附上简单的代码说明。

没太看懂题目，统计每行里字符a的数目？

读行并统计a的数目 -> 链表

试试这段代码

#include <stdio.h>
#include <string.h>

int cal(char * s)
{
    int n, i, j, k;

    n = strlen(s);
    for(j = 0, i = 1; i <= n / 2 && j < i; i += j < i)
    if(n % i == 0)
    for(k = n, j = 0; j < i && k >= n; j += k >= n)
    for(k = j + i; k < n && s[k] == s[j]; k += i);

    return n / i;
}

int main()
{
    char s[128];
    for(; gets(s)[0] != '.'; printf("%d\n", cal(s)));
    return 0;
}

测试了一下，OJ上说有一个小bug，能不能讲解一下思路。。代码看了一会貌似好难看懂= =

同楼上问，b版的代码太精简了额

呵呵说的这么客气。亲自去试了一下结果是某个数据参考输出为5时我的代码居然没有输出。

没有输出那就是说我的程序终止了，意味着这个数据的第一个字符是"."。（我的程序结束条件即是如此）

于是又重新阅读了一遍题目，重点落在了最后一句话——当输入为一个“.”时，输入结束。

呵呵，差一点都不行。这意味着"."是可以出现在数据字符串中的，当且仅当该串只包含一个"."时才作为结束标志。

于是修改了代码重新提交。AC。

#include <stdio.h>
#include <string.h>

int cal(char * s)
{
    int n, i, j, k;

    n = strlen(s);
    for(j = 0, i = 1; i <= n / 2 && j < i; i += j < i)
    if(n % i == 0)
    for(k = n, j = 0; j < i && k >= n; j += k >= n)
    for(k = j + i; k < n && s[k] == s[j]; k += i);

    return n / i;
}

int main()
{
    char s[128];
    for(; strcmp(gets(s), "."); printf("%d\n", cal(s)));
    return 0;
}

写成这样是不是好理解一些？

简单解释一下cal中各变量的意义：

n：字符串的长度

i：测试子串的长度，它应该能整除n

j：子串内的偏移量

k：以j为基点，i为步长的偏移量，用于指向各个子串的相同偏移位置。以测试各子串相同位置的字符是否相等。

#include <stdio.h>
#include <string.h>

int cal(char * s)
{
    int n, i, j, k;

    n = strlen(s);
    for(i = 1; i <= n / 2; i++)
    {
        if(n % i) continue;
        for(j = 0; j < i; j++)
        {
            for(k = j + i; k < n && s[k] == s[j]; k += i);
            if(k < n) break;
        }
        if(j == i) break;
    }

    return n / i;
}

int main()
{
    char s[128];
    for(; strcmp(gets(s), "."); printf("%d\n", cal(s)));
    return 0;
}

有兴趣可以对比一下两段代码。算法完全相同，第一段只是用逻辑表达式代替了第二段中的判断跳转语句。

这也用一个实例验证了break、continue这两种跳转方式也不是必须的。更何况goto

[ 本帖最后由 beyondyf 于 2014-11-3 22:19 编辑 ]

真的很赞！学习啦

恩。。清晰了很多。。谢谢斑竹大大。么么哒。。最后贴上自己刚AC的代码。。算法上
跟斑竹大大的代码是一样的算是给这个帖子这道题目一个结束吧。= =话说斑竹大大你的等级好高啊o_o

#include<stdio.h>
#include<string.h>
int main()
{
    char s[110];
    int l,i,j,flag;

    while(strcmp(gets(s),".") != 0)
    {

        l = strlen(s);
        for(i = 1; i <= l / 2; i++)
        {
            flag = 0;
            if(l % i != 0)
            {
                continue;
            }
            for(j = i; j < l; j += i)
            {
                if(strncmp(&s[j],s,i) != 0)
                {
                    flag = 1; //flag = 1 表示不相等
                    break;
                }
            }
            if(flag == 1)
            {
                continue;
            }
            else
            {
                printf("%d\n",l / i);
                break;
            }

        }
        if(i == l)
        {
            printf("%d\n",l / i);
        }

    }
    return 0;
}