hdu3746（next數組解決）

題目大意：給一個字元串，問你向尾部或首部最少加幾個可以使這個字元串由n個相同的小字元串組成，且n > 1。

題目的要點：1、首尾皆可以加字元；

                    2、 要求最短重複子串；

                    3、 重複次數必須大于1；

然後就是怎麼解決了。我的解決方法是next數組，舉個例子吧：

字元串： a    b    c    a    b    c    a    b    c    a    \0

next[ ] : -1    0    0    0    1    2    3    4    5    6    7

結果是:  cir = len - next[len]     cir就是最短重複子串的長度

             if(len%cir == 0)     那麼就不用加（前提是cir != 0,也就是隻重複一次的時候）

             x = cir - (len%cir)    就是要添加的字元個數

       其實當next數組成遞增趨勢上升時（要持續上升不是斷斷續續那種），就是第二個最短重複子串從第二個字元開始的next數組，進而我們也可以看做next數組從後面開始算重複數組，也就是它是向字元串串首加字元，然而我們也可以看出其實從首或是從尾加，答案并不變的。

下面是代碼實作：

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>

using namespace std;

char str[];
int nt[];
void get_next()
{
    int len = strlen(str);
    int i = , j = -;

    nt[] = -;
    while(i < len)
    {
        if(j == - || str[i] == str[j])
            nt[++i] = ++j;
        else
            j = nt[j];
    }
    return ;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", str);

        get_next();

        int len = strlen(str);
        int cir = len - nt[len];

        if(len%cir ==  && cir != len)
            printf("0\n");
        else
            printf("%d\n", cir-(len%cir));
    }
    return ;
}
           

若有錯，請大家多多指教~~~