Finding substring in string in Java

Question

I am writing a program to search for a substring in a string in Java without using any Java library.

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

It works for the following input:

• str1="rahul" str2="My name is rahul"
• str1="rahul" str2="rahul sah"
• str3="rahul" str2="sah rahul"

The problem occurs when I specify input as:

• str1="rahul" str2="rararahul"
• str1="rahul" str2="My name is sunil"

It goes into an endless cycle. Can anyone take a look at my piece of code and help me.

  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 suggested using String.contains() - this is java.lang code, not a Java library. However, you obviously want to learn how you could do it yourself. One way to do this is to look at the source code of OpenJDK 7 on String.contains() , which uses String.indexOf() under covers. You can see the (fairly simple) algorithm that they use there.

Problem with your code

Interestingly, your code works for "rahul" and "rararahul" when I embed it in my dev environment. However, there is an infinite loop in the event of a mismatch. This will happen for any str2 containing any of the characters str1 . This is because as soon as you find a match for any character in str1 on the string str2, you reset your variables to start over. Actually, your output is enough to debug it if you look at the sequence that goes through each line.

Possible fix

If you want to continue your own approach and learn from it, then consider stopping and making a small paper design your own approach. You are looking for str1 to appear in str2 . Therefore, you probably want to swap your loops. Then you can be more effective. You can traverse the longer character String ( str2 ) by a character in the outer loop. Then you really need to go into the inner loop if the first character of the shorter line ( str1 ) matches the character you are working with in str2 .

eg. for a bit of your code loop

  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; 

Please note: this will not be fast, but it should work. I tested all the string patterns you provided. You also get a bonus - he will find several matches. If you do not want this (just want true false), break out when he says "Continuing to search ..."

As others have said, if you want to continue your source code, of course, do not try to change the loop variables (i.e. ii) in the inner loop. This is a bad practice, hard to read and prone to many mistakes.

Answer 2

at the beginning of the block with

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

you set ii back to zero. And that's why ii will never be greater than or equal to len1

Answer 3

You need to put the outer loop for jj and the inner loop for ii:

  int ii=0; 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; } } 

EDIT: You also initialize the inner for loop for each character in the larger line. You do not need two loops. I changed it accordingly. That should work.

Answer 4

You can use one loop and a matching condition where the search will begin when the first char is found in the full string. And then the search will continue where the match will be one from the list. Well, here I gave an example to explain.

  public static boolean subString2(String smallString, String fullString) { int k = 0; for (int i = 0; i < fullString.length(); i++) { System.out.println("fullStringCharArray[i]: " + fullString.charAt(i)); if (smallString.charAt(k) == fullString.charAt(i)) { System.out.println("Found: " + smallString.charAt(k)); k++; if (k == smallString.length()) return true; } else { k = 0; } } return false; } 

Here, what is going on, we are going to search in fullString. if the first char of your smallString 'rahul' is equal to 'r', then until it is found, the other part of the string ('ahul') will not be matched. so when "r" matches, it will try to find "a" and then "h" and more. So, if the search value true (k) is equal to the length of smallString, then the substring exists. Hope I could explain correctly. Sorry for my English.

Answer 5

Use this code. This will help you both very short and clear.

 public static boolean subString(String str1, String str2) { int str1Len = str2 == null ? 0 : str1.length(); int str2Len = str2 == null ? 0 : str2.length(); for (int i = 0; i < str2Len; i++) { if (str1.charAt(0) == str2.charAt(i)) { int count = 0; for (int j = 0; j < str1Len; j++) { if (str1.charAt(j) == str2.charAt(i)) { i++; count++; } } if (count == str1Len) { return true; } } } return false; }