字符串----HDU-1358

　　

　　

　　题目大意：求字符串的前缀是否为周期串，若是，打印出循环节的长度以及循环次数。

　　这道题考察的是KMP算法中next数组的应用，必须理解透next[]数组代表的含义才t能通过它解决这道题。思路是先构造出 next[] 数组，下标为 i，定义一个变量 t = i - next[i] 就是next数组下标和下标对应值的差，如果这个差能被下标i整除，即 i%t==0 ,则说明下标i之前的字符串（周期性字符串长度为 i）一定可以由一个前缀周期性的表示出来，这个前缀的长度为刚才求得的那个差，即 t，则这个前缀出现的次数为 i/t 。所以最后输出 i 和 i/t 即可。

　　代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class HDU1358 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> list = new ArrayList<String>();
        
        while(true){
            int n = scanner.nextInt();
            if(n==0) break;
            String s = scanner.next();
            list.add(s);
        }
        for(int j = 0;j<list.size();j++){
            String s = list.get(j);
            
            int []next = next(s);
            System.out.println("Test case #"+(j+1));
            boolean flag = false;
            for(int i=2;i<next.length;i++){
                int k = next[i];
                int t = i-k;
                if (i%t==0&&i/t>1) {
                    System.out.println(i +" "+i/t);
                }
            }
            // if (!flag) System.out.println(0+" "+0);
            System.out.println();
        }
    }

    private static int[] next(String s) {
        if(s==null||s.length()==0)return null;
        int[]next = new int[s.length()+1];
        next[0] = -1;
        if(s.length()==1) return next;
        next[1] = 0;
        int j = 1;
        int k = next[j];
        while(j<s.length()){
            if(k==-1||s.charAt(j)==s.charAt(k)){
                next[++j] = ++k;
            }else {
                k = next[k];
            }
        }
        return next;
    }

}

　　结果：