我正在尝试用Java实现上述算法。但是我遇到了越界异常,并且我不知道如何解决这个问题。
我只是逐行翻译伪代码。
这是代码:
public static int[] computePrefixFunction(String input)
{
int[] pi = new int[input.length()];
int k = 0;
for (int q = 1; q < input.length(); q++) {
char target = input.charAt(q);
while (k > 0 && input.charAt(k) != target) k = pi[k - 1];
if (input.charAt(k) == target) k++;
pi[q] = k;
}
return pi;
}
public static Queue<Integer> KMPMatcher(String T, String P)
{
int n = T.length();
int m = P.length();
int[] pi = computePrefixFunction(P);
int q = 0;
Queue<Integer> Q = new LinkedList<>();
for(int i = 0; i < n; i++)
{
while(q > 0 && P.charAt(q+1) != T.charAt(i))
q = pi[q];
if(P.charAt(q+1) == T.charAt(i))
q = q + 1;
if(q == m-1) // you match it when q reaches size of pattern -1. :)
{
Q.add(i-m+1); // Change it as well.
q = pi[q];
}
}
return Q;
}
public static void main(String[] args) {
System.out.println(KMPMatcher("bdacabdacb","bda"));
}
编辑:我已经使用下面的 piyush 实现更新了代码,纠正了我的一些问题。但是还有另一个问题。
我使用这些测试了 KMPMatcher:
1) System.out.println(KMPMatcher("bacabab","bab"));//返回
[2,4]
2) System.out.println(KMPMatcher("bdacabdacb","bab"));//返回
[3]
数字 1 应该只返回 4,数字 2 应该只返回空列表。为什么会发生这种情况?我试图用这些输入绘制轨迹并将其与伪代码进行比较。我认为这与 if(q==m-1)
中的索引有关(因为它与伪代码版本相比没有比较正确的东西?),我不知道如何修理它。有什么帮助吗?
最佳答案
问题出在 if
语句中。它不应该是 if (q == m-1)
。
public static int[] computePrefixFunction(String input)
{
int[] pi = new int[input.length()];
int k = 0;
for (int q = 1; q < input.length(); q++) {
char target = input.charAt(q);
while (k > 0 && input.charAt(k) != target) k = pi[k - 1];
if (input.charAt(k) == target) k++;
pi[q] = k;
}
return pi;
}
public static Queue<Integer> KMPMatcher(String T, String P)
{
int n = T.length();
int m = P.length();
int[] pi = computePrefixFunction(P);
int q = 0;
Queue<Integer> Q = new LinkedList<>();
for(int i = 0; i < n; i++)
{
while(q > 0 && P.charAt(q) != T.charAt(i))
q = pi[q-1];
if(P.charAt(q) == T.charAt(i))
q++;
{
Q.add(i-q+1); // Change it.
q = pi[q-1];
}
}
return Q;
}
public static void main(String[] args) {
System.out.println(KMPMatcher("bdacabdacb","bda"));
}
关于Java:KMP匹配器算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35459142/