Finding substring in a string in Java

Question

I am writing a program to find substring in the string in Java without using any Java Library.

I had written a function subString(String str1, String str2) as shown below.

It is working for the following input:

1. str1="rahul" str2="My name is rahul"
2. str1="rahul" str2="rahul sah"
3. str3="rahul" str2="sah rahul"

The problem occurs when I give input as:

1. str1="rahul" str2="rararahul"
2. str1="rahul" str2="My name is sunil"

It goes to infinite loop. Can anyone have a look into my code snippet and help me out.

    public static boolean subString(String str1, String str2) {
        boolean found = false;
        int len1 = str1.length();
        int len2 = str2.length();
        int status = 0;
        char[] arr1 = new char[len1];
        char[] arr2 = new char[len2];
        for (int ii = 0; ii < len1; ii++) {
            arr1[ii] = str1.charAt(ii);
        }
        for (int jj = 0; jj < len2; jj++) {
            arr2[jj] = str2.charAt(jj);
        }
        for (int ii = 0; ii < len1; ii++) {
            for (int jj = 0; jj < len2; jj++) {
                if (arr1[ii] == arr2[jj]) {
                    if (ii < len1 - 1) {
                        System.out.println("Found1::" + "arr1::" + arr1[ii]
                                + "and arr2::" + arr2[jj]);
                        found = true;
                        ii++;
                    } else if (arr1[ii] == arr2[jj] && ii == len1 - 1) {
                        System.out.println("Found2::" + "arr1::" + arr1[ii]
                                + "and arr2::" + arr2[jj]);
                        found = true;
                        break;
                    }
                } else if (found == false && arr1[ii] != arr2[jj]) {
                    System.out.println("Found3::" + "arr1::" + arr1[ii]
                            + "and arr2::" + arr2[jj]);
                    found = false;

                } else if (found == true && arr1[ii] != arr2[jj]) {
                    System.out.println("Found4::" + "arr1::" + arr1[ii]
                            + "and arr2::" + arr2[jj]);
                    found = false;
                    ii = 0;
                }
            }
        }
        return found;
    }
}

Answer 1

Others have suggested using String.contains() - which is java.lang code, rather than a Java library. However, you obviously want to explore how you could do this yourself. One way to do that is to look at the OpenJDK 7 source code for String.contains(), which under the covers uses String.indexOf(). You can see the (fairly basic) algorithm they use there.

Problem with your code

Interestingly, your code works for "rahul" and "rararahul" when I paste it into my dev environment. The infinite loop on non matching exists, though. This will occur for any str2 that contains any of the characters of str1. This is because once you find a match of any character in str1 within str2, you reset your variables to start again. Your output is actually enough to debug that, if you look at the sequence that it goes through each string.

Possible fix

If you want to pursue your own approach and learn from that then consider stopping and doing a little design on paper with your own approach. You're looking for an occurence of str1 in str2. So you probably want to swap your loops around. Then you can be more efficient. You can go through the longer String (str2) character by character in the outer loop. Then you only really need to go into the inner loop if the first character of the shorter string (str1) matches the character you're dealing with in str2.

e.g. for the loop bit of your code

    boolean retFound = false;

    for (int jj = 0; jj < len2; jj++) {
        if (arr1[0] == arr2[jj]) {
            boolean tempFound = true;
            int foundIndex = jj;
            for (int ii = 0; ii < len1; ii++) {
                if (arr1[ii] != arr2[jj+ii]) {
                    tempFound = false;
                    break;
                 }
             }

             if (tempFound) {
                  System.out.println("Found substring " + str1 + " in " + str2 + " at index " + foundIndex);
                  System.out.println("Carrying on to look for further matches...");
                  tempFound = false;
                  retFound = true;
             }
        }
   }

   return retFound;

Note, this won't be fast, but it should work. I've tested on all the string samples you provided. You get a bonus too - it will find multiple matches. If you don't want that (just want true false), break out when it says "Carrying on to look for..."

As others have said, if you want to continue with your original code, certainly don't try to change loop variables (i.e. ii) within the inner loop. That's bad practice, hard to read and prone to lots of bugs.

Answer 2

in the block startin with

} else if (found == true && arr1[ii] != arr2[jj]) {

you set ii back to zero. And thats why ii never will be bigger or equals len1