nextarray.java

利用KMP算法

import java.io.*;
import java.util.*;

public class NextArray{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        while(true){
            System.out.println("请输入待处理的字符串: ");
            s = br.readLine();
            if (s.equals("finish"))
                return;
            if (s.length() == 0){
                System.out.println("要处理的字符串不能为空,请重新输入");
                continue;
            }
            int length = s.length();
            int next[] = new int[length];
            getNextArray(s, next);
            System.out.print("您所输入的字符串的next数组是："); 
            printIntArray(next);
	    System.out.println();
        }
        
    }
    public static void getNextArray(String strInput, int[] next){ //length>=1
        int length = strInput.length();
        next[0] = 0;
        if (length == 1) return;
        next[1] = 1;
        if (length == 2) return;

        for (int i=2; i<length; i++){
            int max = 1;
            for (int j=1; j<i; j++){
                String left = strInput.substring(0, j);
                String right = strInput.substring(i-j, i);
                if (left.equals(right)) max = j+1;
            }
            next[i] = max;
        }
    }
    public static void printIntArray(int[] intArray){
        for (int i=0; i<intArray.length; i++)
            System.out.print("" + intArray[i] + " ");
        System.out.println();
    }
}