首页 > 专题系列 > Java解POJ > POJ 2406 Power Strings [解题报告] Java
2013
11-11

POJ 2406 Power Strings [解题报告] Java

Power Strings

问题描述 :

Given two strings a and b we define a*b to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).

输入:

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

输出:

For each s you should print the largest n such that s = a^n for some string a.

样例输入:

abcd
aaaa
ababab
.

样例输出:

1
4
3

温馨提示:

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

解题代码:

import java.util.Scanner;   
public class Main {   
    public static void main(String[] args) {   
        Scanner scn = new Scanner(System.in);         
        String input = "";   
        while(scn.hasNext()){   
            input = scn.next(); 
             if(input.equals(".")){  
                break;
             } 
            System.out.println(kmp(input)); 
        }   
    }   
  
    private static int kmp(String input) {   
        int len = input.length();   
        int[] next = new int[len + 1];   
       
        int i = 0,j = -1;   
        next[0] = -1;   
        while(i < len){   
            if( j == -1 || input.charAt(i) == input.charAt(j)){   
                i++;   
                j++;   
                next[i] = j;   
            }else{   
                j = next[j];   
            }   
        }   
        
        if(len % (len - next[len]) == 0){   
            return len /(len - next[len]);   
        }   
        return 1;   
    }   
}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。