经典kmp算法实现

　　package com.zeny.algorithm;  /**  * @Description TODO  * @Author 千楼  * @Version 1.0  **/ public class Code {      public static int getIndexOf(String s, String m) {         if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {             return -1;         }         char[] str1 = s.toCharArray();         char[] str2 = m.toCharArray();         int i1 = 0;         int i2 = 0;         //O(M)         int[] next = getNextArray(str2);         //O(N)         while (i1 < str1.length && i2 < str2.length) {             if (str1[i1] == str2[i2]) {                 i1++;                 i2++;             } else if (next[i2] == -1) {                 i1++;             } else {                 i2 = next[i2];             }         }         return i2 == str2.length ? i1 - i2 : -1;     }      public static int[] getNextArray(char[] ms) {         if (ms.length == 1) {             return new int[] {-1};         }         int[] next = new int[ms.length];         next[0] = -1;         next[1] = 0;         int i = 2;         int cn = 0;         while (i < next.length) {             if (ms[i - 1] == ms[cn]) {                 next[i++] = ++cn;             } else if (cn > 0) {                 cn = next[cn];             } else {                 next[i++] = 0;             }         }         return next;     }      public static void main(String[] args) {         String s = ＂abcabcababaccc＂;         String m = ＂cab＂;         int index = getIndexOf(s, m);         System.out.println(index);     } }