首页 > 专题系列 > Java解POJ > POJ 1961 Period [解题报告] Java
2013
11-10

POJ 1961 Period [解题报告] Java

Period

问题描述 :

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 AK ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.

输入:

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.

输出:

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.

样例输入:

3
aaa
12
aabaabaabaab
0

样例输出:

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

解题代码:

//* @author:
import java.util.Scanner;   
  
public class Main {   
    static int next[]=new int[1000010];

    public static void main(String[] args) {   
        Scanner scn = new Scanner(System.in); 
        int n;        
        String input = "";   
        int j=0;
        int k=0;
        while(scn.hasNext()){  
            n=scn.nextInt(); 
            input = scn.next(); 
             if(n==0){  
                break;
             } 
           getNext(input,n);
           System.out.printf("Test case #%d\n",++k);
           

           /* 挨个试验 */ 
          for (int i = 2; i <= n; i++){ 
            /* 计算首尾重复子串的长度 */
            j = i - next[i];
            /* 串满足重复性质且重复子串不为本身 */
             if (i % j == 0 && i / j > 1){
                System.out.printf("%d %d\n", i, i / j); 
              }
           }
           System.out.printf("\n");
        }   
       
      
    }   

   public static void getNext(String T,int len) {//建立模式串T的next[]表
    int i = 0;
    int j = next[0] = -1;
	
    while (i< len)
     if (0 > j || T.charAt(i) == T.charAt(j)) {//匹配
        j++; i++;
        next[i] = j;
     }else//失配
       j = next[j];
  }
}

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n