hdu3746 KMP的next数组应用,求项链首尾项链循环

题意:
      给你一个项链,问你最少加多少个珠子能满足整个项链是一个循环的项链(首尾相连)


思路:
     KMP的简单应用只要了解next数组的意义就好说了,下面总结下
 next在循环方面的常用应用
(1)i - next[i] 最小循环节(第一个字母开始)
(2)next[i] 最大循环节中的第几位数(此时循环节可交叉)
(3)next[i] != 0 && i % (i - next[i]) == 0,当前是循环节中的最   后一位.
(4)在(3)的前提下 i / (i - next[i]) 表示的最大周期个数,也就是在最小循环节的前提下的最大周期个数。那么这个题目就好办了,先求出,如果next[n] && n % (n - next[n])

直接输出0,因为此时最后一个是循环节上的数字,并且是最后一个。否则就输出(n - next[n]) - n % (n - next[n])


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

#define N 100000 + 100

int next[N];
char str[N];

void get_next(int m)
{
    int j ,k;
    j = 0 ,k = -1;
    next[0] = -1;
    while(j < m)
    {
        if(k == -1 || str[j] == str[k])
        next[++j] = ++k;
        else
        k = next[k];
     }
     return ;
}

int main ()
{
    int t ,i ,m;
    scanf("%d" ,&t);
    while(t--)
    {
       scanf("%s" ,str);
       m = strlen(str);
       get_next(m);
       if(next[m] && m % (m - next[m]) == 0)
       puts("0");
       else
       printf("%d
" ,(m - next[m]) - m % (m - next[m]));
    }
     return 0;
} 
        



原文地址:https://www.cnblogs.com/csnd/p/12063116.html