1 public class Main { 2  3     public static void main(String[] args) { 4         String s = "abcabcababaccc"; 5         String m = "ab"; 6          7         System.out.println(getIndex(s, m)); 8     } 9 10     public static int getIndex(String s, String m) {11         if(s.length() < m.length()) {12             return -1;13         }14 15         char[] str1 = s.toCharArray();16         char[] str2 = m.toCharArray();17         18         int i1 = 0;19         int i2 = 0;20 21         int[] next = getNextArray(str2);22 23         while(i1 < str1.length && i2 < str2.length) {24             if(str1[i1] == str2[i2]) {25                 i1++;26                 i2++;27             } else if(next[i2] == -1) {28                 i1++;29             } else {30                 i2 = next[i2];31             }32         }33 34         return i2 == str2.length?i1-i2:-1;35     }36 37     public static int[] getNextArray(char[] str) {38         if(str.length == 1) {39             return new int[]{-1};40         }41 42         int[] next = new int[str.length];43         next[0] = -1;44         next[1] = 0;45 46         int i = 2;47         int cn = 0;48 49         while(i < next.length) {50             if(str[i-1] == str[cn]) {51                 next[i++] = ++cn;52             } else if(cn > 0) {53                 cn = next[cn];54             } else {55                 next[i++] = 0;56             }57         }58 59         return next;60     }61 }