POJ 2406 KMP算法next数组理解

时间：2022-12-11 18:51:19
Power Strings
Time Limit: 3000MS        Memory Limit: 65536K
Total Submissions: 43624        Accepted: 18200
Description
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input
Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output
For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

题意：

题意：给出一个串，问你这个最多是多少个相同的字串重复连接而成的。如：ababab则最多有3个ab连接而成。

 

本来想水水字符串题找找自信，结果。。。。碰到了复杂的KMP算法，next数组的理解。。。由于时间比较干，资料暂时存下，以后有时间去好好研究。


以下是得到next数组的代码：

void GetNext(char* t, int* next)
{
    int i, j, len;
    i = 0;
    j = -1;
    next[0] = -1;
    while(t[i] != '\0')
    {
        if (j == -1 || t[i] == t[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}
当一个字符串以0为起始下标时，next[i]可以描述为"不为自身的最大首尾重复子串长度"。

有一个原串和一个副串。

AC代码：

#include<cstdio>
#include<cstring>
const int N=1000000+5;
char s[N];
int next[N];
void get_next(char s[],int len)
{
    int i=0;
    int j=-1;
    next[0]=-1;
    while(i<=len)
    {
        if(j==-1||s[j]==s[i])
            next[++i]=++j;
        else
            j=next[j];
    }
}
int main()
{
    while(scanf("%s",s))
    {
        if(s[0]=='.')
            break;
        int len=strlen(s);
        get_next(s,len);
        int k=len-next[len];
        int ans;
        if(len%k==0)
            ans=len/k;
        else
            ans=1;
        printf("%d\n",ans);
    }
    return 0;
}

网上其他人的理解：

思路：KMP中的get_next(),或者get_nextval()，对next数组的应用。next[len]是最后一个字符跳的步长，如果他有相同字符串，则该串长度是len-next[len]（这点我还在想要怎么证明！）...如果整个长度len能分解成x个这种串（能整除），就得到ans了。否则不能分解。只能是由他自己组成串，长度为1。

用 length - next[length] 求出"不为自身的最大首尾重复子串长度"，此时需要多求一位next[length]值，若最大重复子串的长度是length的非1整数倍，则证明字符串具有周期重复性质。

#include<iostream>
#include<cstring>
using namespace std;
const int Max = 100000005;

 

charstr[Max];       //  模式串。
int len, next[Max];

 

void get_next(){
    int i = 0, j= -1;
    next[0] =-1;
    while(i< len){
       if(j == -1 || str[i] == str[j]){
           ++i; ++j;

           next[i] = j;
       } 
       else j = next[j];
    }
}

 

int main(){
   while(scanf("%s", str) != EOF){
       if(str[0] == '.') break;
       len = strlen(str);
       get_next();
       int ans = 1;
       if(len % (len-next[len]) ==0)      //  看整个长度len能分解成x个这种串。
           ans = len / (len-next[len]);
       printf("%d\n", ans);
    }
    return0;
}

 

next[]数组：

POJ 2406 KMP算法next数组理解





标签：

相关文章