匹配字符串的KMP算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

其中next序列,表示子串的前后缀最大匹配长度. 例如对于字符串C[], next[i]表示子串c[0 .. i]中, 前缀与后缀的最大匹配长度.

举例如果子串是 abcuab, 其前缀是a, ab, abc, abcu, abcua, 后缀是 b, ab, uab, cuab, bcuab, 其中匹配的最大子串是ab, 长度是2.

按定义挨个计算next的值

public static int[] getNexts(char[] tt)
{
int[] nexts = new int[tt.length];
nexts[0] = 0;
// 从1到结束, 挨个计算next
for (int i = 1; i < tt.length; i++)
{
// 在给定的子串里, 记录matched时, 最大的长度值
for (int j = 0; j < i; j++)
{
boolean matched = true;
// 使用 k, 依次比较从 0 到 j 和从 i-j 到 i的字符是否相等, 注意下标都是从小往大移动
for (int k = 0; k <= j; k++)
{
if (tt[k] != tt[i-j+k])
{
matched = false;
break;
}
} // 匹配的, 记录最大长度
if (matched)
{
int length = j + 1;
if (nexts[i] < length)
nexts[i] = length;
}
}
} return nexts;
}

改进后的方法, 在遍历中依次记录next的值, 令循环减少许多

/**
* 只使用两个起始下标, 来计算和记录next序列
*
* @param tt
* @return
*/
public static int[] getNexts2(char[] tt)
{
int[] nexts = new int[tt.length]; nexts[0] = 0;
// 前缀起始下标
int prefix = 0;
// 后缀起始下标
int suffix = prefix + 1;
// 匹配长度
int len = 0;
while(suffix < tt.length)
{
if (tt[prefix] == tt[suffix])
{
// 如果匹配, 则记录下当前的next最大值, 并且将前缀和后缀下标都往大移动一位
prefix++;
len++;
if (nexts[suffix] < len)
nexts[suffix] = len;
}
else
{
// 如果不匹配, 则当前长度归零, 并且前缀回归起点, 而后缀依然往后走
len = 0;
prefix = 0;
}
suffix++;
} return nexts;
}

字符串搜索过程:

public static int kmpFind(char[] ss, char[] tt)
{
// 内容串下标
int spos = 0;
// 搜索串下标
int tpos = 0; // 计算next序列
int[] nexts = getNexts2(tt);
while (spos < ss.length)
{
if (ss[spos] == tt[tpos])
{
// 匹配上后, 判断是否满足退出条件
if (tpos == tt.length - 1) return spos - tt.length + 1;
if (tpos == ss.length - 1) return -1;
// 否则继续往后匹配
spos++;
tpos++;
}
else
{
// 未匹配的情况下, 如果搜索串是第一步都未中, 则内容串下标继续移动
if (tpos == 0)
spos++;
// 否则调整搜索串下标到前一步的next值(忽略掉最大前缀)
else
tpos = nexts[tpos - 1];
}
} return -1;
}