Match:Power Strings(POJ 2406)

                Match:Power Strings(POJ 2406)

                字符串前缀的阶

  题目大意:求前缀的阶

  和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];
}
}

  Match:Power Strings(POJ 2406)

  另外以这一题有散列做法,但是没有kmp那么快,但是用到了一个非常好的算法——矩阵快速幂,以后补

上一篇:php编译 :virtual memory exhausted: Cannot allocate memory


下一篇:函数计算: 让小程序开发进入 Serverless 时代