首页 > 代码库 > poj------2406 Power Strings

poj------2406 Power Strings

2024-07-14 11:28:14   221人阅读

A - Power Strings 难度：☆☆
Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
Submit Status Practice POJ 2406

Description

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).

Input

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.

Output

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

Sample Input

abcdaaaaababab.

Sample Output

143

Hint

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

 from http://poj.org/problem?id=2406

考察kmp算法中的next数组....

next的两种表示方法，第一种是前缀next[]数组...

while(i<len){    if(-1==j||ss[i]==ss[j])    {        i++;        j++;        next[i]=j;     }    else  j=next[j];}

 

另种表示方法文为：

while(i<len){   if(j==-1||ss[i]==s[j]) {     i++:     j++;     if(ss[i]==ss[j])    {         next[i]=next[j];    }    else  next[i]=j; }  else  j=next[j];}

 

 这道题是考察有多少个重复的最大n所以我们不妨看他的回溯长度len_D=len(已经匹配的位置) --next[len](对应部分的匹配值);

 

Java代码：

  

 1 //package dek0; 2  3 import java.util.Scanner; 4  5 public class Main {     6      7     public static void main(String args[]) 8     { 9         Scanner  reader = new Scanner(System.in);10         String ss="";11         while(reader.hasNext())    12         {13            ss=reader.next();14            if(ss.charAt(0)==‘.‘) break;15            int len=ss.length();16            int next[]=new int [len+1];17                next[0]=-1;18            int i=0,j=-1;19            while(i<len)20            {21                if(j==-1||ss.charAt(i)==ss.charAt(j))22                {23                  i++;24                  j++;25             /*     if(ss.charAt(i)==ss.charAt(j))26                          next[i]=next[j];27                  else      next[i]=j;*/28                  next[i]=j;29                }30                else  j=next[j];31            }32            if(len%(len-next[len])==0)33              System.out.println(len/(len-next[len]));34            else35                System.out.println(1);36         }37     }38 }

 

 


联系
我们