28
\$\begingroup\$

I created my own indexOf function. I was wondering if anyone could help me come up with a way to make it more efficient. I am practicing for interviews so the catch is that I cannot use any String methods. I believe the runtime of this method is O(n2) with space of O(n). Correct me if I am wrong.

Also, I want to ensure the program runs safely and correctly, the only test case I can think of it the length comparison.

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;
}
\$\endgroup\$
  • 6
    \$\begingroup\$ Wikipedia has a list of string substring searching algorithms with their time and space complexity. The faster it goes, the more complicated (and cool and innovative!) it is, but knowing the internals of a nice and fast one could be something to talk about in an interview, perhaps? en.wikipedia.org/wiki/String_searching_algorithm \$\endgroup\$ – Patashu Mar 12 '14 at 0:24
16
\$\begingroup\$

There is a problem in your code and this hilights it :

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");
    }
}

Good reviews have been given and I have nothing to add.

Edit : additional details for what it is worth :

  • an additional test case should be added to check that first occurence is found
  • your implementation corresponds to the naive way of searching. In the litterature, you'll find other algorithms with potentially better performances.
\$\endgroup\$
  • \$\begingroup\$ Good spotting... for what it is worth, I have never been certain I like the String.indexOf("") handling in Java.... \$\endgroup\$ – rolfl Mar 11 '14 at 21:51
  • \$\begingroup\$ Your answer goes through all tests properly so you implicitly agree with this behavior ;-) (and have my +1) \$\endgroup\$ – SylvainD Mar 11 '14 at 21:54
  • \$\begingroup\$ I really appreciate the test cases! thank you!! \$\endgroup\$ – Liondancer Mar 12 '14 at 15:53
  • \$\begingroup\$ I think some of the test cases are switched around. The ones that are commented with a match, do not match. \$\endgroup\$ – Liondancer Mar 12 '14 at 16:34
  • \$\begingroup\$ Well I'm not quite sure what you mean but in any case, your function should probably have a behaviour as close as possible to the original method. Let me know (or fell free to edit my answer) if there is anything wrong. \$\endgroup\$ – SylvainD Mar 12 '14 at 22:15
31
\$\begingroup\$

Complexity

Pedantically, the time-complexity is \$ O( m \times n ) \$, where m is str.length and n is substr.length. This matters when \$ \left| m-n \right| \$ is large.

The Space complexity is \$ O(1) \$. You do not allocate any size-based memory structures.

Safety

It all looks good. There are no threading issues, no leaks, no problems.

Correctly

Nope, I don't like the lack of neat handling for invalid inputs.... you should be null-checking, etc. Getting a raw 'NullPointerException' looks bad.

Edit: Note that Josay has pointed out that your code (and my code below) produce different behaviour to String.indexOf() when the search term is the empty-string/empty-array.

Alternative

I think your code is fine, but... I tend to use loop break/continue more than most... and, this saves a bunch of code in this case...

Also, for readability, I often introduce a limit variable when the loop-terminator can be complicated....

Consider the following loops which do not need the count variable:

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;
\$\endgroup\$
15
\$\begingroup\$

One thing which does not seem to have been mentioned in other answers,

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

Instead of checking less than x plus one. You can do less than or equal to x.

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

I find this a bit easier to read and understand.

This can also be applied to the monkey's (@rolfl's) code:

int limit = len - sublen;
searchloop: for (int i = 0; i <= limit; i++) {
...
\$\endgroup\$
13
\$\begingroup\$

This looks good to me.

For efficiency, you have two options:

  1. Reduce the number of operations in the inner loop. Let's look at that.

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

    Here, the addition j+i seems like something you should be able to, somehow, replace with a single initial addition outside the loop, and an increment inside the loop. There also seems to be correlation between j and count (if anyone which line you are on, you'll have either count == j or count == j+1. It follows that the test j < sublen is false if and only if count == sublen it true, so you could probably get rid of one of them.

    At this point I want to emphasise that this kind of analysis will give you performance increases so small that they are almost certainly not worth the effort. That leads us to:

  2. Look for a different algorithm. This is likely the only way to get a significant increase in performance. A good place to start is the classical Boyer-Moore algorithm.

    For complexity, recall the inputs:

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

    If str is of length n and substr is of length m, your implementation executes the outer loop roughly n times and, in the worst case, each of those n iterations executes the inner loop m times. The running time of your implementation is thus no worse than O(n*m).

    When considering space complexity, one should not count the space used for inputs, only the additional space used. Your implementation uses only a fixed number of variables (len, sublen, count, i) of primitive type. The amount of space it uses is independent of the sizes n and m of the input strings, and so we say that your implementation uses "constant space", written O(1).

    Finally, I want to mention that your implementation is not far from the actual implementation of the Java standard library; check it out here.

\$\endgroup\$
  • \$\begingroup\$ I wish Java had an array type which could be read and written as 1, 2, 4, or 8 byte values; many kinds of string-related algorithms could benefit from processing things in multi-character chunks, even if one would have to use special-case logic for different alignments, and to handle the starting and ending bits of a string (e.g. to look for the string "ABRACADABRA", start by examining every other 64-bit word, ignoring everything that isn't ABRA, CADA, BRAC, ADAB, RACA, DABR, or ACAD). Either endianness could be simulated at a cost of at most one extra instruction per access. \$\endgroup\$ – supercat Mar 12 '14 at 18:31
9
\$\begingroup\$

Other answers are already covering what maybe matters more to you: space, time complexity, safety, correctness. I think you can do further steps in order to improve the code readability: if it was a production code it would be hard to maintain. Consider the following suggestions:

  • variables should go nearest their utilization as possible: avoid broad global declaration as far as you can;
    • for example, why is count initialized before the first exit point, that is where it could never be used? It should go just before the for instruction (the first for? - on a first reading I couldn't say it)
  • len - sublen + 1 should be stored in a final variable (constant) with a good name: what does it mean that value?
  • the default return value (-1) should be declared in one point, with a meaningful name (no magic numbers). What if later you would want to change the default not-found value?
  • the function has three exit points, with a further break in a nested loop, causing a difficult reading of its logical branches (they remember insane gotos)
  • the main exit point count == sublen should go inside a meaningful boolean variable: why is this an exit condition? How would you explain it to your coworker?

If you want to see a different approach to indexOf (but on byte arrays) you could check the following code, with also should be more readable:

    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;
    }

(Original post)

\$\endgroup\$
  • \$\begingroup\$ This is not really a code review answer, is it? At least you should explain in how far the code would help to improve the ops code. \$\endgroup\$ – ChrisWue Mar 12 '14 at 18:51
  • \$\begingroup\$ I proposed it because I think it is more readable. What do you mean by "ops code"? And where can I find code review's rules? Thanks \$\endgroup\$ – robermann Mar 12 '14 at 19:01
  • \$\begingroup\$ With "ops" I meant "OP's" (Original Poster's). There are some discussions on meta around what a good code review is. Basically your answer would be more useful if you include some explanation of why and how your version is more readable. \$\endgroup\$ – ChrisWue Mar 12 '14 at 19:41
  • \$\begingroup\$ I've just updated the answer with my considerations on code readability - I hope I made my point clearer, thanks for your feedbacks \$\endgroup\$ – robermann Mar 12 '14 at 20:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.