2013
11-11

# 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]）
这里写错了吧。