Finding index of first substring

Question

I wrote this function to find the index of the first substring. I was wondering if you can help me find some flaws or possibly help increase performance?

Example:

str = "happy" substr = "app"

index = 1

My code:

public static int subStringIndex(String str, String substr) {
    int substrlen = substr.length();
    int strlen = str.length();
    int j = 0;
    int index = -1;

    if (substrlen < 1) {
        return index;
    }
    else {
        for (int i = 0; i < strlen; i++) {              // iterate through main string
            if (str.charAt(i) == substr.charAt(j)) {    // check substring
                index = i - j;                              // remember index
                j++;                                    // iterate
                if (j == substrlen) {                   // when to stop
                    return index;
                }
            }
            else {
                j = 0;
                index = -1;
            }
        }
    }
    return index;
}

Answer 1

You can get away without the index variable as you're reassigning it at each step of your loop anyway.

public static int subStringIndex(String str, String substr) {
    int substrlen = substr.length();
    int strlen = str.length();
    int j = 0;

    if (substrlen >= 1) {
        for (int i = 0; i < strlen; i++) {              // iterate through main string
            if (str.charAt(i) == substr.charAt(j)) {    // check substring
                j++;                                    // iterate
                if (j == substrlen) {                   // when to stop
                    return i - substrlen; //found substring. As i is currently at the end of our substr so sub substrlen
                }
            }
            else {
                j = 0;
            }
        }
    }
    return -1;
}

Answer 2

Just checking that you intend to be reinventing-the-wheel, you can do:

System.out.println("happy".indexOf("app"));

You did know that, right?

Or, if you want to reformat the 'signature' to match yours, it is:

public static int subStringIndex(String str, String substr) {
    return str.indexOf(substr);
}

There are a number of helper methods on String which will help:

• String.indexOf(substr) - return the index of the first occurrence of substr
• String.indexOf(substr, start) - return the index of the first occurrence of substr on or after the start position.
• String.lastIndexOf(substr) - return the index of the last occurrence of substr
• String.lastIndexOf(substr, start) - return the index of the last occurrence of substr starting before the start position.
-

Answer 3

Actually there is a bug. Consider str="aaS" and substr="aS". At first iteration a and a are equal. At second iteration a and S are not equal, and it will skip it, however substr's first character is equal to it.

So it should be:

public static int subStringIndex(String str, String substr) {
    int substrlen = substr.length();
    int strlen = str.length();
    int j = 0;

    if (substrlen >= 1) {
        for (int i = 0; i < strlen; i++) {              // iterate through main string
            if (str.charAt(i) == substr.charAt(j)) {    // check substring
                j++;                                    // iterate
                if (j == substrlen) {                   // when to stop
                    return i - (substrlen - 1); //found substring. As i is currently at the end of our substr so sub substrlen
                }
            }
            else {
                i -= j;
                j = 0;
            }
        }
    }
    return -1;
}

Edit update:

Needed to subtract 1 from the String's length in order to pass the right answer.

Answer 4

Here is another version:

public static int indexOf(String original, String find) {

    if (find.length() < 1)
        return -1;

    boolean flag = false;
    for (int i = 0, k = 0; i < original.length(); i++) {
        if (original.charAt(i) == find.charAt(k)) {
            k++;
            flag = true;
            if (k == find.length())
                return i - k + 1;
        } else {
            k = 0;
            if (flag) {
                i--;
                flag = false;
            }
        }
    }

    return -1;
}

Answer 5

My re-writing: clear and clean, yet efficient. There is no innovation in the algorithm. Just the way of the coding in more structural re-arrangement, trying to make the thought and steps easy to read and understand (comments are welcome):

static int subStringIndex( String str, String substring) {
    if (substring.length() < 1 )
        return -1;

    int L = str.length();
    int l = substring.length();
    int index = -1;

    for (int i = 0, j; i <= L-l; i++) {
    // if the remaining (L-i) is smaller than l, 
    // there won't be no enough length to contain the substring.
        for (j = 0; j < l; j++) {
            if (substring.charAt(j) != str.charAt(i+j) ) {
                    break;
            } 
        }
        // has it reached the end of the shorter string? 
        // if so, it means no non-equals encountered.
        if (j == l) {
            index = i;
            break;
        }
    }

    return index;
}