KMP Algorithm — Pattern Matching in O(N+M)

int[] buildLPS(String p) {
  int[] lps = new int[p.length()];
  int len = 0;
  for (int i = 1; i < p.length(); ) {
    if (p.charAt(i) == p.charAt(len)) { lps[i++] = ++len; }
    else if (len > 0) len = lps[len - 1];
    else lps[i++] = 0;
  }
  return lps;
}

void kmp(String t, String p) {
  int[] lps = buildLPS(p);
  int i = 0, j = 0;
  while (i < t.length()) {
    if (t.charAt(i) == p.charAt(j)) { i++; j++; if (j == p.length()) { match(i - j); j = lps[j - 1]; } }
    else if (j > 0) j = lps[j - 1];
    else i++;
  }
}