介绍
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度。参考——百度百科
题目
给定两个字符串，查找一个字符串是否包含另一个字符串，如果包含，返回该字符串的起始下标
思路分析
- 首先理清变量，假设从str1字符串中查找str2字符串是否存在以及存在的起始位置。
解法一： 暴力枚举，遍历str1的每个字符的位置，依次比对两个字符相应位置的字符，如果str2字符串的指针走到了最后，则表示当前匹配成功，返回当前str1的其实位置
解法二： KMP算法
- 首先获取一个关于str2的记录每个位置最长公共前后缀的数组，记为preNextArr。
- preNextArr的具体含义：在当前位置之前所有字符构成的字符串中，头部和尾部完全一样的字符串长度，前缀不包括最后一个字符，后缀包括第一个字符。
- 遍历str1数组，如果遍历到str2的某个位置发现 str1[i] 不等于 str2[i], 则跳转到preNextArr数组中记录的位置继续比较。
暴力枚举代码
class Solution {
// 暴力解法
public int strStr(String haystack, String needle) {
// 首先进行边界条件判断
if(haystack == null || needle == null || haystack.length() < needle.length()){
return -1;
}
if("".equals(needle)) return 0;
char[] charH = haystack.toCharArray();
char[] charN = needle.toCharArray();
for(int i = 0; i + charN.length - 1 < charH.length; i++){
int ch = i;
int cn = 0;
while(cn < charN.length && charH[ch] == charN[cn]){
ch++;
cn++;
}
if(cn == charN.length){
return i;
}
}
return -1;
}
}
KMP算法
// KMP 算法主体
public static int getIndexOf(String s, String m) {
// 首先进行边界条件的判断，如果有一个为空，或者s长度小于m， 则一定无法匹配，直接返回-1
if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
return -1;
}
// 将s和m改造为字符数组
char[] ss = s.toCharArray();
char[] ms = m.toCharArray();
// 创建两个指针进入while循环，si表示s的索引，mi表示m的索引
int si = 0;
int mi = 0;
int[] next = getNextArray(ms);
// 结束条件是si和mi其中有一个遍历完了整个字符数组
while (si < ss.length && mi < ms.length) {
if (ss[si] == ms[mi]) {
// 决策一：如果当前s和m位置的元素相等，则两个指针均向后面移动
si++;
mi++;
} else if (next[mi] == -1) {
// 决策二： 如果不相等，且此时m位于字符数组的起始位置，那么直接将s向后移
si++;
} else {
// 决策三； 如果不想等，但此时的m不在起始位置，则s不懂， m调正到next【mi】的位置继续向相面比较
mi = next[mi];
}
}
// 等到循环结束时，s和m一定有一个已经全部遍历完了，如果时m遍历完了，则找到了m，否则返回-1
return mi == ms.length ? si - mi : -1;
}
// 给定一个字符串的字符数组，返回一个数组表示每个元素之前字符串的最长公共前后缀，0位置默认-1，1位置默认0；
public static int[] getNextArray(char[] ms) {
// 如果数组只有一个元素，默认返回-1；
if (ms.length == 1) {
return new int[] { -1 };
}
// 创建一个数组，默认和原始数组等长，使得每个位置的元素信息都可以知道
int[] next = new int[ms.length];
// 初始化0和1位置上的元素
next[0] = -1;
next[1] = 0;
// 给定两个变量pos和cn进入while循环，pos表示当前元素的位置，cn表示当前元素前面一位的元素最长公共前后缀（就是前面那一位的next[pos - 1]）
int pos = 2;
int cn = 0;
while (pos < next.length) {
if (ms[pos - 1] == ms[cn]) {
// 如果前面一位元素与前缀的后一位相等，则next【pos】再前一位的cn基础上+1
next[pos++] = ++cn;
} else if (cn > 0) {
// 如果不相等的话，那么cn指向前缀的后面一位，继续进入循环，此处pos没有进行自增操作，还是在原来的位置
cn = next[cn];
} else {
// 此处如果cn == 0 ，则表示前一位的最长公共前后缀不存在，而且此时，mas[pos - 1] != ms[cn] ，则此位置的公共前后缀也一定为0
next[pos++] = 0;
}
}
// 返回结果集next数组
return next;
}
public static void main(String[] args) {
String str = "abcabcababaccc";
String match = "ababa";
System.out.println(getIndexOf(str, match));
}
网友评论