记录一道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;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/159834.html
