Knuth-Morris-Pratt算法混淆

Question

我正在尝试实现KMP算法。我的算法在下面的示例中正确工作

• 文本: 121121
• 模式: 121
• 结果: 1,4

但是当文本为12121且模式与上面相同时，结果只是: 1.我不知道这是算法的问题还是我的实现的问题？

其他例子：

• 文本: 1111111111
• 格局: 111
• 结果: 1,4,7

我的代码是：

public class KMP {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String text = reader.readLine();
        String pattern = reader.readLine();
        search(text,pattern);
    }
    private static void search(String text,String pattern)
    {
        int[] Pi = Pi(pattern);
        for (int i = 0,q=0; i <text.length()&&q<pattern.length() ; i++,q++) {
            while (q>=0 && pattern.charAt(q)!=text.charAt(i))
            {
                q=Pi[q];
            }
            if(q==pattern.length()-1) {
                System.out.println(i-pattern.length()+2);
                q=Pi[q];
            }

        }
    }

    private static int[] Pi(String p) {
        int[] Pi = new int[p.length()];
        Pi[0]=-1;
        int i=0;
        int j=-1;
        while (i<p.length()-1) {
            while (j>=0 && p.charAt(j)!=p.charAt(i))
            {
                j=Pi[j];
            }
            i++;
            j++;
            if(p.charAt(j)==p.charAt(i)) Pi[i]=Pi[j];
            else Pi[i]=j;
        }
        return Pi;
    }

}

Answer 1

希望能帮助你。

public int strStr(String source, String target) {

    if (source == null || target == null){
        return -1;
    }
    if (source.isEmpty() && !target.isEmpty()){
        return -1;
    }
    if (source.isEmpty() && target.isEmpty()){
        return 0;
    }
    if (target.isEmpty()){
        return 0;
    }

    int index = 0;
    int compare_index = 0;
    int compare_start_index = 0;
    int compare_same_length = 0;
    List<Integer> answers = new ArrayList<Integer>();

    while (true){
        if (compare_same_length ==0){
            compare_start_index = compare_index;
        }

        if (source.charAt(compare_index) == target.charAt(index)){
            compare_same_length++;
            index++;
        } else {
            if (compare_same_length >0){
                compare_index--;
            }
            compare_same_length = 0;
            index = 0;
        }

        compare_index++;
        if (compare_same_length == target.length()){
            answers.add(compare_start_index+1);
            compare_same_length=0;
            index=0;
        }

        if (compare_index == source.length()){
            //here are answers
            for (int i = 0; i < answers.size(); i++) {
                int value = answers.get(i);
            }
            return 1;
        }
    }
}