前缀和后缀

image.png
image.png
image.png

  1. 通过前缀和后缀获得每一个字符前边的所有字符前缀和后缀最大匹配长度

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