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:

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

The problem occurs when I give input as:

str1="rahul" str2="rararahul"
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;
    }
}

Never change the controlvariable of a loop inside the loop. That is bad practice. — Jens
– Jens, Commented Jan 28, 2015 at 6:48
If you don't want to use java inbuild function you shouldn't use String.length() then ... why don't you want to use String.contains? — Valentin Cavel
– Valentin Cavel, Commented Jan 28, 2015 at 6:52
@ValentinCavel probably so he can learn how String.contains works. — Stack Exchange Broke The Law
– Stack Exchange Broke The Law, Commented Jan 28, 2015 at 6:55
I got this question as assignment during my academics many time... — smali
– smali, Commented Jan 28, 2015 at 8:47

J Richard Snape · Accepted Answer · 2015-01-28 07:34:38Z

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.

Jens · Accepted Answer · 2015-01-28 06:51:40Z

3

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

answered Jan 28, 2015 at 6:51

Jens

69.6k15 gold badges107 silver badges133 bronze badges

2 Comments

RS_ingo Over a year ago

Getting incremented at again if the character match is found

Jens Over a year ago

Try to debug. After it is incremented it go to the next condition which will set it back to zero.

vipluv · Accepted Answer · 2015-01-28 07:13:44Z

2

You need to put the outer loop for jj and 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 are also initializing the inner for loop for each character in the larger string. You don't need two loops at all. I have changed it appropriately. This should work.

edited Jan 28, 2015 at 7:13

answered Jan 28, 2015 at 6:49

vipluv

6075 silver badges8 bronze badges

1 Comment

Pham Trung Over a year ago

@abc123 this idea should be correct, however, there are a lot of tiny bugs in OP code, which need to debug very carefully to have a fully working code.

Saqib Rezwan · Accepted Answer · 2015-01-28 07:46:04Z

2

You can use one loop and matching condition where the search will begin when the first char will be found in the full string. And then, the search will continue where where the matching will one by one from the list.Okay, here I am giving 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 happening, we are going to search in fullString. if the first char of your smallString 'rahul' is 'r' then until it is found, the other part of the string ('ahul') will not be matched. so when the 'r' is matched then it will try to search for 'a' and then 'h' and more. So, if the count of search true(k) is equal of smallString length then the substring exists. I hope, I could explain properly. Sorry for my English.

edited Jan 28, 2015 at 7:46

answered Jan 28, 2015 at 7:13

Saqib Rezwan

1,41815 silver badges21 bronze badges

2 Comments

RS_ingo Over a year ago

Inputs are str1="rahul" and str2="raraabcrahul"

Saqib Rezwan Over a year ago

I have updated the code. Please try again. Also for your above input the result should be 'true', right? The result is 'true' for both my old and new codes.

Chamly Idunil · Accepted Answer · 2015-01-28 07:50:14Z

2

Use This Code. This will help you and 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;
    }

answered Jan 28, 2015 at 7:50

Chamly Idunil

1,9001 gold badge20 silver badges34 bronze badges

Comments

LOGOUT · Accepted Answer · 2022-09-17 14:52:44Z

0

      public class Main {
      public static void main(String args[]) {
      Scanner sc=new Scanner(System.in);
      System.out.println("Enter the string");
      String str=sc.nextLine();
      String Str1=" ";
      System.out.println("Enter the numbers");
      int start=sc.nextInt();
      int end=sc.nextInt();
      for (int i = start; i < end; i++)
      Str1 += String.valueOf(str.charAt(i));
      System.out.println(Str1);
      }
      }

answered Sep 17, 2022 at 14:52

LOGOUT

1

1 Comment

Community Over a year ago

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

Collectives™ on Stack Overflow

Finding substring in a string in Java

6 Answers 6

Problem with your code

Possible fix

1 Comment

2 Comments

1 Comment

2 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Problem with your code

Possible fix

1 Comment

2 Comments

1 Comment

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related