String字符串匹配算法
@Date 2017.06.09
暴力匹配
- 时间复杂度O(m * n)
private static int forceMatch(String originS, String matchedS) {
char[] originArray = originS.toCharArray();
char[] matchedArray = matchedS.toCharArray();
int originLen = originS.length();
int matchedLen = matchedS.length();
int i = 0, j = 0;
while (i < originLen && j < matchedLen) {
if (originArray[i] == matchedArray[j]) {
// 相等则继续位移比较(需要同时移位)
i++;
j++;
} else {
// 不相等则长字符串回到原点,重新比较
i = i - j + 1;
j = 0;
}
}
// 匹配字符串完全找到
if (j == matchedLen) {
return i - j;
} else {
return -1;
}
}
KMP匹配
- 时间复杂度O(m + n)
/**
* @param originS 长字符串
* @param matchedS 要匹配的字符串
* @return 匹配字符在长字符串中的位置
*/
private static int kmpMatch(String originS, String matchedS) {
// next 数组各值的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀。
// 例如如果next [j] = k,代表j 之前的字符串中有最大长度为k 的相同前缀后缀
char[] originArray = originS.toCharArray();
char[] matchedArray = matchedS.toCharArray();
int originLen = originS.length();
int matchedLen = matchedS.length();
int[] next = getNext(matchedArray);
int i = 0, j = 0;
while (i < originLen && j < matchedLen) {
if (j == -1 || originArray[i] == matchedArray[j]) {
// 相等则继续位移比较(需要同时移位)
i++;
j++;
} else {
// j != -1,且当前字符匹配失败(originArray[i] != matchedArray[j]),则令 i 不变,j = next[j]
// next[j]即为j所对应的next值
// 失配时,模式串向右移动的位数为:已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
// 失配时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值
j = next[j];
}
}
// 匹配字符串完全找到
if (j == matchedLen) {
return i - j;
} else {
return -1;
}
}
/**
* 获取失配时的位移数组
* 求解原理为:
* 1. 匹配字符串的前缀后缀的公共元素的最大长度值的对应数组
* 2. eg: abab : 0 0 1 2
* 3. 最大对称长度的前缀后缀,然后整体右移一位,初值赋为-1
* 4. eg: abab : -1 0 0 1
* @param matchedArray 需要匹配的pattern字符串
* @return 位移数组
*/
private static int[] getNext(char[] matchedArray) {
int matchedLen = matchedArray.length;
int[] next = new int[matchedLen];
next[0] = -1;
int k = -1;
int j = 0;
while (j < matchedLen - 1) {
// matchedArray[k]表示前缀,matchedArray[j]表示后缀
// matchedArray[j] == matchedArray[k] 此判断是因为matchedArray[j]已经失配,用相同的matchedArray[k], 位移后去匹配一样是失配.
// 故二者相等时,继续递归
if (k == -1 || matchedArray[j] == matchedArray[k]) {
++k;
++j;
next[j] = k;
} else {
k = next[k];
}
}
return next;
}