Custom indexOf() without String methods

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;
}
• 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 – Patashu Mar 12 '14 at 0:24

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.
• Good spotting... for what it is worth, I have never been certain I like the String.indexOf("") handling in Java.... – rolfl Mar 11 '14 at 21:51
• Your answer goes through all tests properly so you implicitly agree with this behavior ;-) (and have my +1) – SylvainD Mar 11 '14 at 21:54
• I really appreciate the test cases! thank you!! – Liondancer Mar 12 '14 at 15:53
• I think some of the test cases are switched around. The ones that are commented with a match, do not match. – Liondancer Mar 12 '14 at 16:34
• 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. – SylvainD Mar 12 '14 at 22:15

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;

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

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.

• 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. – supercat Mar 12 '14 at 18:31

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 {
q.pop();
}
} else {
}
}

return idx;
}
• 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. – ChrisWue Mar 12 '14 at 18:51
• 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 – robermann Mar 12 '14 at 19:01
• 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. – ChrisWue Mar 12 '14 at 19:41
• I've just updated the answer with my considerations on code readability - I hope I made my point clearer, thanks for your feedbacks – robermann Mar 12 '14 at 20:29

protected by Jamal♦Oct 21 '18 at 5:28

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?