Custom indexOf() without String methods

Question

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(n²) 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;
}

Answer 1

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.

Answer 2

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;

Answer 3

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++) {
...

Answer 4

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.

Answer 5

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)