@@ -0,0 +1,1295 @@
+public class KnuthMorrisPratt %7B%0A%0A%09private static int%5B%5D kmp_table(char%5B%5D w) %7B%0A%09%09int pos = 2; // the current position we are computing in t%0A%09%09int cnd = 0; // the zero-based index in W of the next character of the%0A%09%09%09%09%09%09// current candidate substring%0A%0A%09%09int%5B%5D t = new int%5Bw.length%5D;%0A%09%09t%5B0%5D = -1;%0A%09%09t%5B1%5D = 0;%0A%09%09while (pos %3C w.length) %7B%0A%09%09%09if (w%5Bpos - 1%5D == w%5Bcnd%5D) %7B // the substring continues%0A%09%09%09%09cnd++;%0A%09%09%09%09t%5Bpos%5D = cnd;%0A%09%09%09%09pos++;%0A%09%09%09%7D else if (cnd %3E 0) // it doesn't, but we can fall back%0A%09%09%09%09cnd = t%5Bcnd%5D;%0A%09%09%09else %7B // we have run out of candidates. Note cnd = 0%0A%09%09%09%09t%5Bpos%5D = 0;%0A%09%09%09%09pos++;%0A%09%09%09%7D%0A%09%09%7D%0A%0A%09%09return t;%0A%09%7D%0A%0A%09private static int kmp_search(char%5B%5D s, char%5B%5D w) %7B%0A%09%09int m = 0; // the beginning of the current match in s%0A%09%09int i = 0; // the position of the current character in w%0A%0A%09%09int%5B%5D t = kmp_table(s);%0A%09%09while (m + i %3C s.length) %7B%0A%09%09%09if (w%5Bi%5D == s%5Bm + i%5D) %7B%0A%09%09%09%09if (i == w.length - 1)%0A%09%09%09%09%09return m;%0A%09%09%09%09i++;%0A%09%09%09%7D else %7B%0A%09%09%09%09if (t%5Bi%5D %3E -1) %7B%0A%09%09%09%09%09m += i - t%5Bi%5D;%0A%09%09%09%09%09i = t%5Bi%5D;%0A%09%09%09%09%7D else %7B%0A%09%09%09%09%09i = 0;%0A%09%09%09%09%09m++;%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%09%09%7D%0A%0A%09%09// if we reach here, we have searched all of s unsuccessfully%0A%09%09return s.length;%0A%09%7D%0A%0A%09public static void main(String%5B%5D args) %7B%0A%09%09char%5B%5D s = %22whatthemomooofun%22.toCharArray();%0A%09%09char%5B%5D t = %22moo%22.toCharArray();%0A%0A%09%09System.out.println(kmp_search(s, t));%0A%09%7D%0A%0A%7D%0A

Create KnuthMorrisPratt.java