记录一道KMP的题目，
这道题对于刚接触kmp的同学来说算是一道不错的题目了，
能够帮助我们理解得更深刻...
题目：小明的字符串
题目描述
小明有两个字符串，分别为 S,T。
请你求出 TT 串的前缀在 S 串中出现的最长长度为多少。
输入描述
输入包含两行，每行包含一个字符串，分别表示 S,T。
1 < |S|,|T| < 10^6 ，保证 S,T 只包含小写字母。
输出描述
输出共 1 行，包含一个整数，表示答案。
输入输出样例
示例 1
输入
aabba
abb
输出
3
示例 2
输入
aabba
aba
输出
2
运行限制
最大运行时间：1s
最大运行内存: 256M
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str1 = scanner.nextLine(); String str2 = scanner.nextLine(); int[] next = kmpNext(str2); int temp; for (int i = str2.length(); i > 0; i--) { temp = kmpSearch(str1, str2.substring(0, i), next); if (temp != -1) { System.out.println(temp); break; } } } private static int kmpSearch(String str1, String str2, int[] next) { int j = 0; for (int i = 0; i < str1.length(); i++) { while (j > 0 && str1.charAt(i) != str2.charAt(j)) j = next[j - 1]; if (str1.charAt(i) == str2.charAt(j)) j++; if (j == str2.length()) return str2.length(); } return -1; } private static int[] kmpNext(String str2) { int[] next = new int[str2.length()]; int j = 0; for (int i = 1; i < str2.length(); i++) { while (j > 0 && str2.charAt(i) != str2.charAt(j)) j = next[j - 1]; if (str2.charAt(i) == str2.charAt(j)) j++; next[i] = j; } return next; } }
