题目大意:求前缀的阶
和POJ1961是一样的,KMP的Next数组的应用,不要用STL,不要一个一个读入字符(IO永远是最慢的)
#include <iostream>
#include <algorithm>
#include <functional>
#include <string.h> using namespace std; static char Text[];
static int _Next[]; void Input(int &);
void Get_Next(const int); int main(void)
{
int Length, k_count, if_res;
while ()
{
Input(Length);
if (*Text == '.')//小数点结束
break;
Get_Next(Length);
if_res = Length % (Length - _Next[Length]);
k_count = Length / (Length - _Next[Length]);
if (if_res == && k_count > )
printf("%d\n", k_count);
else printf("1\n");
}
return EXIT_SUCCESS;
} void Input(int &Length)
{
Length = ;
scanf("%s", Text);
Length = strlen(Text);
} void Get_Next(const int Length)
{
int i = , k = -;
_Next[] = -; while (i < Length)
{
if (k == - || Text[i] == Text[k])
{
i++;
k++;
_Next[i] = k;
}
else k = _Next[k];
}
}
另外以这一题有散列做法,但是没有kmp那么快,但是用到了一个非常好的算法——矩阵快速幂,以后补