当前位置：网站首页>poj1961 Period(KMP)

poj1961 Period(KMP)

2022-08-08 17:24:00 【51CTO】

C - Period

Crawling in process...

Crawling failed

Time Limit:3000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64u

Submit Status Practice POJ 1961

System Crawler (2016-05-10)

Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A ^K ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.

Input

The input consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S.The second line contains the string S. The input file ends with a line, having the
number zero on it.

Output

For each test case, output "Test case #" and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.

Sample Input

       
       3
       
aaa
       
12
       
aabaabaabaab
       
0
      
1.
2.
3.
4.
5.

Sample Output

       
       Test case #1
       
2
       
3
       
Test case #2
       
2
       
2
       
3
       
4
      










第二次做KMP算法了可惜的是我见到了都不知道是要用KMP算法做唉

上次做也没有深刻理解next数组的意义做了这道题让我理解到（仅仅是我的理解，错了别喷我。。）next数组的作用就是在匹配主串的时候

遇到了不相同的字符通过next数组快速跳过已经匹配过的字符。具体解释请看这位大牛写的

做了这道题也知道了next数组可以找循环节唉真的想不到

       
       #include <stdio.h>
       
       int 
       
       next[
       
       1000000
       
       +
       
       10];
       
       char 
       
       str[
       
       1000000
       
       +
       
       10];
       
       int 
       
       n;
       
       void 
       
       set_next()
       
{
       
       int 
       
       i
       
       =-
       
       1;
       
       int 
       
       j
       
       =
       
       0;
       
       next[
       
       0]
       
       =-
       
       1;
       
       while(
       
       j
       
       <
       
       n)
       
  {
       
       if(
       
       i
       
       ==-
       
       1
       
       ||
       
       str[
       
       i]
       
       ==
       
       str[
       
       j])
       
    {
       
       i
       
       ++;
       
       j
       
       ++;
       
       next[
       
       j]
       
       =
       
       i;
       
    }
       
       else
       
       i
       
       =
       
       next[
       
       i];
       
  }
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       t
       
       =
       
       0;
       
       while(
       
       ~scanf(
       
       "%d",
       
       &
       
       n)
       
       &&
       
       n)
       
  {
       
       scanf(
       
       "%s",
       
       str);
       
       set_next();
       
       printf(
       
       "Test case #%d\n",
       
       ++
       
       t);
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++)
       
    {
       
       // printf("%d\n",next[i]);
       
       int 
       
       length
       
       =
       
       i
       
       -
       
       next[
       
       i];
       
       if(
       
       i
       
       !=
       
       length
       
       &&
       
       i
       
       %
       
       length
       
       ==
       
       0)
       
       printf(
       
       "%d %d\n",
       
       i,
       
       i
       
       /
       
       length);
       
    }
       
       printf(
       
       "\n");
       
  }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15742657/5556624

当前位置：网站首页>poj1961 Period(KMP)

poj1961 Period(KMP)

边栏推荐

猜你喜欢

随机推荐