POJ 1961 C++ （KMP）

POJ 1961 C++ （KMP）2011-04-18蜗牛

#include<iostream>
using namespace std;
int n,next[1000008];
char s[1000008];
void Get_next（）
{int j,k;
j=1;
k=0;
next[1]=0;
while（j<=n+1）
    { if（k==0 || s[j]==s[k]）
      { j++;
       k++;
       next[j]=k;
       }
     else
       k=next[k];
     }
}
int main（）
{ int i,cnt,k;
  freopen（"in.txt","r",stdin）;
  freopen（"out.txt","w",stdout）;
  k=1;
 while（scanf（"%d
",&n）,n！=0）
     { for（i=1;i<=n;i++）
        s[i]=getchar（）;
      s[i]="#";
      Get_next（）;
      printf（"Test case #%d
",k++）;
      for（i=2;i<=n;i++）
        if（i%（i+1-next[i+1]）==0）
          { cnt=i/（i+1-next[i+1]）;
           if（cnt！=1）
           printf（"%d %d
",i,cnt）;
           }
    printf（"
"）;
   }
  return 0;
}

该题的题意是这样的，给若干个字符串，判断该字符串的前n位最多重复了几次，比如，给ababab，结果是前4位重复了2次，前6位重复了3次，忽略重复一次的情况.现在我们将注意力放在一个给定的字符串重复了多少次，然后做一个循环就可以求出所有的结果。

我们要根据kmp算法中的next函数来解决这个问题，以ababab为例加以说明：

String：ababab

Next： 0112345

这里根据后面的需要多计算了一位next值。

我们用ababab即作为主串有作为模式串来进行匹配，假设匹配到第7为时不匹配了（下标中 1开始），要根据next[7]（=5）的值继续匹配：

ababab*

ababab&

ababab*

ababab

这样，我们用（length+1）-next[length+1]就是字符串向右移动的位数，在该例中为7- 5=2.然后用总的长度除以这个向右移动的位数，如果能除尽的话，结果就是重复的次数，否则重复的次数为1