java - 这种模式查找方法是否比 KMP 或 Z 算法实现更好？

Question

我正在尝试编写 KMP 算法。搞定后，我用java字符串的方法试了一下。以下是我的实现方式:

String str = "This is easier version of fist";
    String pattern = "is";
    String[] splitStr = str.split(pattern);
    System.out.println("Total occurence of the given pattern in the given string is ="
            +(splitStr.length-1));
    int i=1, count=0;
    for(String st: splitStr){
        if(i<splitStr.length){
        count += st.length();
        System.out.println("Occurence of "+i+" pattern is at index "+count);
        count+=pattern.length();
        i++;
        }
    }

我得到以下输出:

Total occurence of the given pattern in the given string is =3
Occurence of 1 pattern is at index 2
Occurence of 2 pattern is at index 5
Occurence of 3 pattern is at index 27

我知道 java split() 方法的时间复杂度是 O(string length)。上面的代码对 KMP 的实现如何公平？另外，如果我在模式匹配案例的采访中而不是 KMP 给出这个答案，这是明智之举还是我只是在浪费机会？

Answer 1

编辑:我修复了之前的复杂度计算。

KMP 实现以复杂度 O(n + m) 运行，其中 n = str.length() 和 m = pattern.length()。

您的算法也以复杂度 O(n + m) 运行，但它可以跳过正确匹配并产生错误答案。

考虑这个测试用例:

String str = "apple-orange-apple-apple-apple-orange-apple";
String pattern = "apple";

您的代码出现了 4 次。应该是 5 吧？

这个案例:

String str = "appleappleappleapple";
String pattern = "apple";

我认为这并没有破坏你的机会，因为它表明你能够用 Java 编写逻辑代码并提出解决方案。

祝你面试顺利。