# 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 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.... Mar 11 '14 at 21:51
• Your answer goes through all tests properly so you implicitly agree with this behavior ;-) (and have my +1) Mar 11 '14 at 21:54
• I think some of the test cases are switched around. The ones that are commented with a match, do not match. 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. Mar 12 '14 at 22:15
• @Josay sorry I wasn't clear. What I meant was in your test cases, compareFunc("BC", "ABCD"); I think you meant compareFunc("ABCD", "BC");? Because there isn't an actual match in any of the middle, beginning, and end cases you provided. I am assuming this is what you wanted to do. Mar 13 '14 at 2:41

## 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. 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();