Finds a pattern in a string by returning index of where the pattern starts in the string in Java

Question

This is the challenge I tried in Codefights: Avoid using built-in functions to solve this challenge. Implement them yourself, since this is what you would be asked to do during a real interview. Implement a function that takes two strings, s and x, as arguments and finds the first occurrence of the string x in s. The function should return an integer indicating the index in s of the first occurrence of x. If there are no occurrences of x in s, return -1. How can I make it faster? Thanks in advance. Here's my code, which is still slow for larger input cases(string of around 10^6 characters):

int findFirstSubstringOccurrence(String s, String x) { 
   int j=0;
   for (int i=0; i<=(s.length()-x.length()); i++) {
       j=0;
       while ((j<x.length()) && s.charAt(i+j)==x.charAt(j)){
           j++;
       }
       if (j == x.length()) 
           return i;
       if(s.charAt(i+j)!=s.charAt(i))
           i += j;
   }
   return -1;
}

Answer 1

Naming

findFirstSubstringOccurrence is quite a long name. substringIndex is shorter and still very explicit about what it does.

---

Your parameters are not named very well. When calling your method, how do you know which of the strings is the substring and which one the containing string? I suggest the method header int substringIndex(string containing, string candidate).

Style

Your use of white space is very unconventional. Usually you would have spaces around operators for example.

---

Using braces around one liners makes your code prettier and more readible, and also prevents bugs when you add a line without noticing the missing braces. Instead of this:

if(s.charAt(i+j)!=s.charAt(i))
    i += j;

write this:

if (s.charAt(i + j) != s.charAt(i)) {
    i += j;
}

---

Your initialization of j is redundant, since you assign 0 at the start of the loop anyway. So just declare it before the loop, then assign it in the loop.

Performance

Expecting the likely case that your string does not contain the substring candidate and returning early can improve your performance in many cases, so check before looping whether the candidate is longer than the containing string.

---

After finding the first occurence of the first letter of the candidate in the containing string, the next improvement would be to check whether the last letter of the candidate is at position firstLetterPosition + candidateLength - 1. That allows you to quickly find situations, where only a part of the substring is contained. Then you can check the middle part.