import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
/**
* KMP:从长度为m字符串A中找出长度为n的字符串B在字符串A的的位置的算法，算法复杂度O(m+n)
* 算法讲解参考链接：
* http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
* http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
*/
public class KMP {
public static void main(String[] args) {
System.out.printf("请输入主串A:\n");
Scanner scanner = new Scanner(System.in);
String strA = scanner.nextLine();
int lenStrA = strA.length();
int i;
/**
* 字符串A
*/
char[] A = new char[lenStrA];
for (i = 0; i < lenStrA; i++) {
A[i] = strA.charAt(i);
}
System.out.printf("请输入要搜索的串B:\n");
String strB = scanner.nextLine();
int lenStrB = strB.length();
/**
* 字符串B
*/
char[] B = new char[lenStrB];
for (i = 0; i < lenStrB; i++) {
B[i] = strB.charAt(i);
}
System.out.println(A);
System.out.println(B);
KMP kmp = new KMP();
int[] partialMatchTable = generatePartialMatchTable(B);
System.out.println(Arrays.toString(partialMatchTable));
//Integer[] result = kmp.findPostionIndexWithBF(A, B);
Integer[] result = kmp.findPostionIndexWithKMP(A,B,partialMatchTable);
if (result == null || result.length == 0) {
System.out.println("没有找到");
} else {
System.out.println(Arrays.toString(result));
}
}
/**
* 产生部分匹配表：
* -首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
* -举例说明
* 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？
* "部分匹配值"就是"前缀"和"后缀"的【最长】的共有元素的长度。以"ABCDABD"为例，
* － "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
搜索词ABCDABD A B C D A B D
部分匹配值 0 0 0 0 1 2 0
*
* @param str
* @return
*/
public static int[] generatePartialMatchTable(char[] str) {
int len = str.length;
int[] partialMatchTable = new int[len];
for (int i = 0; i < len; i++) {
if (i == 0) {
partialMatchTable[i] = 0;
} else {
for (int j = 0; j < i; j++) {
boolean flag = true;
for (int k = 0, m = j; k <= j; k++, m--) {
if (str[k] != str[i - m]) {
flag = false;
break;
}
}
if (flag) {
/**最大长度那个*/
partialMatchTable[i] = j + 1;
}
}
}
}
return partialMatchTable;
}
/**
* KMP搜索算法
*
* @param master 主串
* @param search 模式串
* @param partialMatchTable 部分匹配表:当比较不相同时，模式串下次比较位置确定之依据
* @return 以数组形式返回模式串在主串里的所有位置
*/
public Integer[] findPostionIndexWithKMP(char[] master, char[] search, int[] partialMatchTable) {
int masterLen = master.length;
int searchLen = search.length;
if (searchLen > masterLen) {
throw new IllegalArgumentException("模式串长度大于主串，无需搜索，肯定不存在");
}
/**
* 存储结果
*/
List<Integer> reuslt = new ArrayList<>();
/**
* 用于记录主串的当前比较位置
*/
int masterCurrentIdx = 0;
/**
* 用于记录模式串的当前比较位置
*/
int seaerchCurrentIdx = 0;
while (true) {
if (master[masterCurrentIdx] == search[seaerchCurrentIdx]) {
// System.out.println("search["+seaerchCurrentIdx+"] = " + search[seaerchCurrentIdx]+" master["+masterCurrentIdx+"] = " + master[masterCurrentIdx]);
masterCurrentIdx++;
seaerchCurrentIdx++;
} else {
int searchReturnIdx = 0;
if(seaerchCurrentIdx > 1){
searchReturnIdx = partialMatchTable[seaerchCurrentIdx-1];
if(searchReturnIdx > 0){
seaerchCurrentIdx = searchReturnIdx;
}else{
masterCurrentIdx = masterCurrentIdx - seaerchCurrentIdx + 1;
seaerchCurrentIdx = 0;
}
}else{
masterCurrentIdx = masterCurrentIdx - seaerchCurrentIdx + 1;
seaerchCurrentIdx = 0;
}
//剩余比较的长度小于模式串的长度,肯定不存在模式串了。
if (masterLen - masterCurrentIdx < searchLen-searchReturnIdx) {//需要减掉重复的长度
break;
}
}
if (seaerchCurrentIdx == searchLen) {
int postionIdx = masterCurrentIdx - seaerchCurrentIdx;
reuslt.add(postionIdx);
/**
* 准备一轮搜索
*/
masterCurrentIdx = postionIdx + 1;
seaerchCurrentIdx = 0;
//剩余比较的长度小于模式串的长度,肯定不存在模式串了。
if (masterLen - masterCurrentIdx < searchLen) {
break;
}
}
/**
* 主串位置到末尾时跳出循环
*/
if (masterCurrentIdx > masterLen - 1) {
break;
}
}
Integer[] realResult = new Integer[reuslt.size()];
return reuslt.toArray(realResult);
}
/**
* 强力搜索[Brute force]简称为BF算法
*
* @param master 主串
* @param search 模式串
* @return 以数组形式返回模式串在主串里的所有位置
*/
public Integer[] findPostionIndexWithBF(char[] master, char[] search) {
int masterLen = master.length;
int searchLen = search.length;
if (searchLen > masterLen) {
throw new IllegalArgumentException("模式串长度大于主串，无需搜索，肯定不存在");
}
/**
* 存储结果
*/
List<Integer> reuslt = new ArrayList<>();
/**
* 用于记录主串的当前比较位置
*/
int masterCurrentIdx = 0;
/**
* 用于记录模式串的当前比较位置
*/
int seaerchCurrentIdx = 0;
while (true) {
if (master[masterCurrentIdx] == search[seaerchCurrentIdx]) {
// System.out.println("search["+seaerchCurrentIdx+"] = " + search[seaerchCurrentIdx]+" master["+masterCurrentIdx+"] = " + master[masterCurrentIdx]);
masterCurrentIdx++;
seaerchCurrentIdx++;
} else {
masterCurrentIdx = masterCurrentIdx - seaerchCurrentIdx + 1;
seaerchCurrentIdx = 0;
//剩余比较的长度小于模式串的长度,肯定不存在模式串了。
if (masterLen - masterCurrentIdx < searchLen) {
break;
}
}
if (seaerchCurrentIdx == searchLen) {
int postionIdx = masterCurrentIdx - seaerchCurrentIdx;
reuslt.add(postionIdx);
/**
* 准备一轮搜索
*/
masterCurrentIdx = postionIdx + 1;
//System.out.println("masterCurrentIdx = " + masterCurrentIdx);
seaerchCurrentIdx = 0;
//剩余比较的长度小于模式串的长度,肯定不存在模式串了。
if (masterLen - masterCurrentIdx < searchLen) {
break;
}
}
/**
* 主串位置到底末尾时跳出循环
*/
if (masterCurrentIdx > masterLen - 1) {
break;
}
}
Integer[] realResult = new Integer[reuslt.size()];
return reuslt.toArray(realResult);
}
}
联系客服
