java - Knuth-Morris-Pratt 算法混淆

Question

我正在尝试实现 KMP 算法。我的算法适用于以下示例

• 文字：121121
• 图案：121
• 结果：1,4

但是当 Text 为 12121 并且 pattern 与上面相同时，结果只是： 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;
        }
    }
}