我的算法就是先找出字符串的长度n，然后求n的所有因数。因为题目中那个字符串a的长度只可能是n的因数。然后就是遍历所有可能的长度，依次去匹配。每一趟匹配的时间复杂度都是O（n）,因为最坏情况下都要走完整个字符串。前面求因数的部分是O（根号n），再加上对因数大小排序O（根号n*logn）。
最后整体的时间复杂度应该是O（n的因数个数*n）。n的因数个数是个什么级别这个就不清楚了，但是肯定超不过O（n^2）的。但如果真的达到了n^2，应该会超时吧。
附上代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 1000000

void q_sort(int*a,int s,int t)
{
    int i,j,tmp;
    if(s<t)
    {
        while(1)
        {
            i = s+1;
            j = t;
            while(i<=t && a[i]<=a[s])    //从左边起，寻找大于分界元素的元素
                i++;
            while(j>s && a[j]>=a[s])     //从右边起，寻找小于分界元素的元素
                j--;

            if(i>=j)
                break;
            //交换a[i]和a[j]
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        if(j!=s)    //交换a[j]和a[s]
        {
            tmp = a[s];
            a[s] = a[j];
            a[j] = tmp;
        }
        q_sort(a,s,j-1);
        q_sort(a,j+1,t);
    }
}

int cmp(char*a,int s1,int t1,char*b,int s2,int t2)    //匹配成功，返回1；否则，返回0。
{
    int i,j;
    int flag;
    i = s1;
    j = s2;
    if((t1-s1)!=(t2-s2))
        return 0;
    flag = 1;
    while(i<=t1 && j<=t2)
    {
        if(a[i]==b[j])
        {
            i++;
            j++;
        }
        else
        {
            flag = 0;
            break;
        }
    }
    return flag;
}

int main()
{
    char s[N+1];
    int i,j,n,m;
    int a[1000];    //存储n的约数
    int top;
    int flag;

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

        //计算n的所有因数
        m = sqrt(n);
        top = 0;
        for(i=1;i<m;i++)
        {
            if(n%i==0)
            {
                a[top++] = i;
                a[top++] = n/i;
            }
        }
        if(m*m==n)
            a[top++] = m;
        else if(n%m==0)
        {
            a[top++] = m;
            a[top++] = n/m;
        }
        //对因数进行排序
        q_sort(a,0,top-1);

        //匹配
        for(i=0;i<top;i++)    //遍历所有可能的长度
        {
            m = n - a[i] + 1;
            flag = 1;    //假设找到了
            for(j=a[i];j<m;j+=a[i])    //进行匹配
            {
                if(cmp(s,0,a[i]-1,s,j,j+a[i]-1))
                    continue;
                else
                {
                    flag = 0;
                    break;
                }
            }

            if(flag)
            {
                printf("%d\n",n/a[i]);
                break;
            }
        }
        gets(s);
    }

    return 0;
}

没有给测试样例，因为我测了题目中的那三组就提交了，然后就过了。