我创建了自己的indexOf函数。我想知道是否有人可以帮助我提出一种提高效率的方法。我正在为面试练习，所以要注意的是我不能使用任何String方法。我相信此方法的运行时间为O（n2），且空间为O（n）。如果我错了，请纠正我。

此外，我想确保程序安全正确地运行，这是我唯一能想到的长度比较的测试用例。

public static int myIndexOf(char[] str, char[] substr) {
    int len = str.length;
    int sublen = substr.length;
    int count = 0;
            if (sublen > len) {
                return -1;
            }
    for (int i = 0; i < len - sublen + 1; i++) {
        for (int j = 0; j < sublen; j++) {
            if (str[j+i] == substr[j]) {
                count++;
                if (count == sublen) {
                    return i;
                }
            } else {
                count = 0;
                break;
            }
        }
    }
    return -1;
}


评论

Wikipedia列出了字符串子字符串搜索算法及其时间和空间复杂性。速度越快，它就越复杂（又酷又创新！），但是了解一个好又快的内部可能是在采访中谈论的话题吗？ zh.wikipedia.org/wiki/String_searching_algorithm

#1 楼

您的代码中有一个问题，这使它显得很重要：

class Class_Test {

    public static int myIndexOf(char[] str, char[] substr) {
        int len = str.length;
        int sublen = substr.length;
        int count = 0;
        if (sublen > len) {
            return -1;
        }
        for (int i = 0; i < len - sublen + 1; i++) {
            for (int j = 0; j < sublen; j++) {
                if (str[j+i] == substr[j]) {
                    count++;
                    if (count == sublen) {
                        return i;
                    }
                } else {
                    count = 0;
                    break;
                }
            }
        }
        return -1;
    }

    public static boolean compareFunc(String s1, String s2)
    {
        int r1 = s1.indexOf(s2);
        int r2 = myIndexOf(s1.toCharArray(), s2.toCharArray());
        boolean ret = (r1==r2);
        System.out.println(ret + " for '" + s1 + "' '" + s2 + "' -> " + r1 + " " + r2);
        return ret;
    }

    public static void main (String[] args)
    {
        // Empty string
        compareFunc("", "");
        compareFunc("A", "");
        compareFunc("AB", "");
        compareFunc("", "A");
        compareFunc("", "AB");
        // Equal non-empty strings
        compareFunc("A", "A");
        compareFunc("AB", "AB");
        compareFunc("ABC", "A");
        // Match at the beginning
        compareFunc("A", "AB");
        compareFunc("AB", "ABC");
        compareFunc("ABC", "ABD");
        // Match at the end
        compareFunc("B", "AB");
        compareFunc("BC", "ABC");
        compareFunc("ABC", "DBC");
        // Match at the middle
        compareFunc("BC", "ABCD");
        compareFunc("CD", "ABCDEF");
        // No match on longer strings
        compareFunc("QWERTYUIOPASDFGHJKL", "ZXCVBNM");
        compareFunc("ZXCVBNM","QWERTYUIOPASDFGHJKL");
        System.out.println("Test successful");
    }
}


给出了很好的评语，我无话可说了。

编辑：有关其价值的其他详细信息：


应该添加一个额外的测试用例，以检查是否发现了第一次出现的情况。
您的实现与简单的搜索方式相对应。在文献中，您会发现其他性能可能更高的算法。


评论

\ $ \ begingroup \ $
很好的发现...对于它的价值，我从来不确定我喜欢Java中的String.indexOf（“”）处理...。
\ $ \ endgroup \ $
–rolfl
2014年3月11日在21:51
\ $ \ begingroup \ $
您的回答正确地通过了所有测试，因此您暗中同意这种行为；-）（并让我+1）
\ $ \ endgroup \ $
– SylvainD
2014年3月11日在21:54
\ $ \ begingroup \ $
我认为有些测试用例已经转换。用匹配项注释的那些不匹配。
\ $ \ endgroup \ $
– Liondancer
2014年3月12日下午16:34
\ $ \ begingroup \ $
我不太清楚您的意思，但是无论如何，您的函数的行为应尽可能接近原始方法。让我知道（或随意编辑我的答案）是否有任何错误。
\ $ \ endgroup \ $
– SylvainD
2014年12月12日22:15
\ $ \ begingroup \ $
@Josay对不起，我不清楚。我的意思是在您的测试用例中，compareFunc（“ BC”，“ ABCD”）;我认为您的意思是compareFunc（“ ABCD”，“ BC”）;？因为您提供的中间，开始和结束案例中都没有实际匹配项。我假设这就是您想要做的。
\ $ \ endgroup \ $
– Liondancer
2014年3月13日在2:41

#2 楼

复杂度

在时间上，时间复杂度为\ $ O（m \ times n）\ $，其中m为str.length和n为substr.length。当\ $ \ left |时这很重要m-n \ right | \ $大。

空间复杂度为\ $ O（1）\ $。您不分配任何基于大小的内存结构。

安全性

看起来不错。没有线程问题，没有泄漏，没有问题。

正确地

不，我不喜欢缺乏对无效输入的整洁处理...。您应该进行null检查等。获取原始的'NullPointerException'看起来很糟糕。

编辑：请注意，乔赛（Josay）指出，当搜索词时，您的代码（和下面的代码）与String.indexOf()产生不同的行为。是空字符串/空数组。

替代方法

我认为您的代码很好，但是...我倾向于使用循环中断/继续比大多数方法更多。 ..并且，在这种情况下，这节省了很多代码...

此外，出于可读性考虑，当循环终止符可能很复杂时，我经常引入limit变量....

考虑以下不需要count变量的循环：

int limit = len - sublen + 1;
searchloop: for (int i = 0; i < limit; i++) {
    for (int j = 0; j < sublen; j++) {
        if (str[j+i] != substr[j]) {
            continue searchloop;
        }
    }
    return i;
}
return -1;


#3 楼

在其他答案中似乎没有提到的一件事，

for (int i = 0; i < len - sublen + 1; i++) {


而不是检查小于x加一的值。您可以做小于或等于x。

for (int i = 0; i <= len - sublen; i++) {


我觉得这更容易阅读和理解。

也可以应用于猴子（@rolfl）的代码：

int limit = len - sublen;
searchloop: for (int i = 0; i <= limit; i++) {
...


#4 楼



为了提高效率，您有两个选择：



减少内部循环中的操作数。让我们看一下。

for (int j = 0; j < sublen; j++) {
    if (str[j+i] == substr[j]) {
        count++;
        if (count == sublen) {
            return i;
        }
    ...
}


这里，添加j+i似乎应该可以用某种方式替换循环外的单个初始添加，在循环内增加。 j和count之间似乎也存在相关性（如果您所在的线路上的任何人，您将拥有count == j或count == j+1。因此，只有当j < sublen为真时，测试count == sublen才为false，因此您可能会摆脱其中一个。

在这一点上，我想强调的是，这种分析将使您的性能提高得如此之小，以至于几乎可以肯定他们不值得付出努力。这导致我们：


寻找不同的算法，这可能是显着提高性能的唯一方法。经典的Boyer-Moore算法是一个很好的起点。

对于复杂性，请回想以下输入：

public static int myIndexOf(char[] str, char[] substr)


如果str的长度为n而substr的长度为m，则您的实现将执行大约n次外部循环，并且最坏的情况是，这n次迭代中的每一次都会执行内部循环m次，因此实现的运行时间不会比O（n * m）。

在考虑空间复杂性时，不应计算用于输入的空间，而应仅计算所使用的额外空间。您的实现仅使用固定数量的基本类型变量（len, sublen, count, i）。它使用的空间量与输入字符串的大小n和m无关，因此我们说您的实现使用“恒定空间”，写为O（1）。

最后，我要提到的是，您的实现与Java标准库的实际实现相距不远。在此处查看。



评论

\ $ \ begingroup \ $
我希望Java具有一个可以以1、2、4或8字节值读写的数组类型。即使需要对不同的对齐方式使用特殊情况的逻辑并处理字符串的开始和结束位（例如查找字符串），许多与字符串相关的算法也可以从处理多字符块中受益。字符串“ ABRACADABRA”，首先检查所有其他64位字，并忽略不是ABRA，CADA，BRAC，ADAB，RACA，DABR或ACAD的所有内容。可以以每次访问最多增加一条额外指令的成本来模拟两种字节序。
\ $ \ endgroup \ $
–超级猫
2014年12月12日18:31

#5 楼

其他答案已经涵盖了可能对您更重要的问题：空间，时间复杂度，安全性，正确性。我认为您可以采取进一步的措施来提高代码的可读性：如果是生产代码，将很难维护。请考虑以下建议：


变量应尽可能接近其利用率：尽可能避免使用广泛的全局声明；例如，


，为什么count在第一个出口点之前被初始化，也就是永远无法使用的地方？它应该在for指令之前（第一个for？-我无法说出它的初读）



len - sublen + 1应该存储在最终变量中（常数），并带有好名：该值是什么意思？
应在一个点中声明默认返回值（-1），并使用有意义的名称（无幻数）。如果以后要更改默认的未找到值怎么办？
该函数具有三个出口点，嵌套循环中还有另一个break，导致难以读取其逻辑分支（它们记住疯狂的goto）
主出口count == sublen应该放在一个有意义的布尔变量内：为什么这是出口条件？

如果您想对indexOf使用其他方法（但在字节数组上），可以检查以下代码，并且也应更易读：

    public static int search(byte[] input, byte[] searchedFor) {
        //convert byte[] to Byte[]
        Byte[] searchedForB = new Byte[searchedFor.length];
        for(int x = 0; x<searchedFor.length; x++){
            searchedForB[x] = searchedFor[x];
        }

        int idx = -1;

        //search:
        Deque<Byte> q = new ArrayDeque<Byte>(input.length);
        for(int i=0; i<input.length; i++){
            if(q.size() == searchedForB.length){
                //here I can check
                Byte[] cur = q.toArray(new Byte[]{});
                if(Arrays.equals(cur, searchedForB)){
                    //found!
                    idx = i - searchedForB.length;
                    break;
                } else {
                    //not found
                    q.pop();
                    q.addLast(input[i]);
                }
            } else {
                q.addLast(input[i]);
            }
        }

        return idx;
    }


（原始帖子）

评论

\ $ \ begingroup \ $
这不是真正的代码审查答案，对吗？至少您应该解释代码在多大程度上有助于改进ops代码。
\ $ \ endgroup \ $
–ChrisWue
2014年12月12日18:51
\ $ \ begingroup \ $
我提出它是因为我认为它更具可读性。您所说的“操作码”是什么意思？在哪里可以找到代码审查的规则？谢谢
\ $ \ endgroup \ $
–罗伯曼
2014年12月12日19:01
\ $ \ begingroup \ $
“ ops”的意思是“ OP's”（原始海报的）。关于meta的讨论，围绕什么是好的代码审查。基本上，如果您对版本为什么以及如何更具可读性进行一些解释，则您的答案会更有用。
\ $ \ endgroup \ $
–ChrisWue
2014年3月12日19:41
\ $ \ begingroup \ $
我刚刚更新了我对代码可读性的考虑-希望我的观点更清楚，谢谢您的反馈
\ $ \ endgroup \ $
–罗伯曼
2014年3月12日20:29在