杭电2549（第一次用java写kmp算法）

点击打开杭电2549

            
clinton
homer
riemann
marjorie
        

            
0
rie 3
        

注意：主要要注意java里内存的控制，和数组的越界情况。（这里坑死我了！！）

import java.util.*;
class Main{
    static int[] next=new int[50005];
    static String str1,str2;
    static int len1,len2;
    public static void main(String args[]){
        int n,i;
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            str2=sc.nextLine();
            str1=sc.nextLine();
            len1=str1.length();
            len2=str2.length();
            n=kmp();
            if(n>0){
                System.out.print(str2.substring(0,n)+" ");//这里要是不用substring，而用for循环，就会超内存。
            }
            System.out.println(n);
        }
    }
    public static void set_next(){
        int i=0,j=-1;
        next[0]=-1;
        while(i<len2){
            if(j==-1||str2.charAt(i)==str2.charAt(j)){
                i++;
                j++;
                next[i]=j;///System.out.print(next[i]+" ");
            }else{
                j=next[j];
            }
        }
        //System.out.println();
    }
    public static int kmp(){
        int i=0,j=0;
        set_next();
        while(i<len1){//System.out.print(j+" ");
            if(j==-1||(j<len2&&str1.charAt(i)==str2.charAt(j))){//c这里不用要j<len2但是java必须要，因为java比较严格，不允许越界情况，而c允许（java通常属于解析型语言，它是一句一句解释，而c是通篇解释）。<span style="font-family: Arial, Helvetica, sans-serif;">同理</span><span style="font-family: Arial, Helvetica, sans-serif;">j==-1一定要放在前面。</span>

                i++;
                j++;//System.out.print("** ");
            }else{
                j=next[j];
            }//System.out.print(j+"* ");
        }//System.out.println();
        return j;
    }
}

原文：http://blog.csdn.net/u011479875/article/details/44996567