CODEWITHSUNDEEP
java
RS_ingo
RS_ingo

Reputation: 429

Finding substring in a string in Java

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;
    }
}

Upvotes: 6

Views: 3342

Answers (6)

LOGOUT
LOGOUT

Reputation: 1

      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);
      }
      }

Upvotes: 0

Chamly Idunil
Chamly Idunil

Reputation: 1872

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;
    }

Upvotes: 2

Saqib Rezwan
Saqib Rezwan

Reputation: 1408

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.

Upvotes: 2

J Richard Snape
J Richard Snape

Reputation: 20344

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.

Upvotes: 11

vipluv
vipluv

Reputation: 607

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.

Upvotes: 2

Jens
Jens

Reputation: 69440

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

Upvotes: 3

Related Questions