HDU 3374 String Problem（最小（大）表示 + KMP）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3374

他左移的步数刚好是最小（大）表示返回的值+1，

然后就是一个关键的结论：同构串个数 == 最小循环节的总个数。。。。

#include <iostream>
#include <cstring>
using namespace std;

char p[1000010];
int nxt[1000010];

//最小表示
int Minp(char *c, int l)
{
    int i = 0, j = 1, k = 0, t;
    while (i < l && j < l && k < l)
    {
        t = c[(i+k)%l] - c[(j+k)%l];
        if (t == 0)
        {
            k++;
        }
        else
        {
            if (t > 0)
            {
                i += k + 1;
            }
            else
            {
                j += k + 1;
            }
            if (i == j)
            {
                j++;
            }
            k = 0;
        }
    }
    return i < j ? i : j;
}


//最大表示
int Maxp(char *c, int l)
{
    int i = 0, j = 1, k = 0, t;
    while (i < l && j < l && k < l)
    {
        t = c[(i+k)%l] - c[(j+k)%l];
        if (t == 0)
        {
            k++;
        }
        else
        {
            if (t < 0)//和最小表示的区别就这里而已
            {
                i += k + 1;
            }
            else
            {
                j += k + 1;
            }
            if (i == j)
            {
                j++;
            }
            k = 0;
        }
    }
    return i < j ? i : j;
}



void GetNext(int l)
{
    int k = -1, j = 0;
    nxt[0] = -1;//别漏
    while (j < l)
    {
        if (k == -1 || p[j] == p[k])
        {
            j++, k++;
            nxt[j] = k;
        }
        else
        {
            k = nxt[k];
        }
    }
}


int main()
{
    int min_index, max_index, l, r;
    while (gets(p) != NULL)
    {
        l = strlen(p);
        GetNext(l);
        min_index = Minp(p, l);
        max_index = Maxp(p, l);
        
        r = l - nxt[l];//最小循环节
        if (l % r == 0)
        {    
            r = l / r;//l/r就是最小循环节的总个数。    
        }
        else
        {
            r = 1;
        }

        printf("%d %d %d %d\n", min_index+1, r, max_index+1, r);
    }
        
    return 0;
}