CODEWITHSUNDEEP
java
Arushi gupta
Arushi gupta

Reputation: 179

To check if a given string contains a substring without using contains or indexOf method

In the following code the problem I am facing is how to make the inner loop start from a given index instead of 0 every time.

LOGIC: 

substr = rohan; 
mainstr = herohanda

The code first check the first character of substr i.e 'r' with every character of mainstr till it finds a match. When a match is found the program return to the outer loop and increments i to check if the 2nd charcater of substr (i.e o) matches the next character(the character next to the index where a match for 'r' was found) of the mainStr. The problem is how to start the inner loop from that next character. Here it is starting with the initial index (0) each time .

CODE:

public class SubstringInString {
   public static void isSubstring(String subStr, String mainStr){
         int flag = 0;
         int counter = 0;
        OUTER: for(int i = flag; i<subStr.length(); i = i+flag){
            INNER:  for(int j = 0; j< mainStr.length(); j=counter ){
                        if(subStr.charAt(i) == mainStr.charAt(j)){
                            counter++;
                            flag++;

                            continue OUTER;
                        }
                        else
                        {
                            if((mainStr.length() - i) >= subStr.length()){
                                counter ++;
                                flag = 0;

                                continue INNER;
                            }

                            else{
                                System.out.println("Main String does not contain the substring");
                            }
                        }
                    }
                }

            //  System.out.println("Match found at " + j-subStr.length());
        }
}

Please tell me what how to solve this and also if there is any better way to do the same. Thanks in advance

Upvotes: 0

Views: 4611

Answers (3)

Shail
Shail

Reputation: 901

Suppose we want to find out if s2 is a substring of s1.

There are 2 base cases:

  1. length of s2 is 0: In this case, we can return true.
  2. length of s2 is more than that of s1: We can return false.

The general approach is as follows: Iterate through each character of s1 and see if it matches with the first character of s2. If it does, then check if rest of the characters of s1 match with rest of the characters of s2. If so, return true. If the s1 is entirely explored with no matches found, return false.

Here is how it would look like in Java: 

static boolean isSubstring(String s1, String s2){
    int n1 = s1.length();
    int n2 = s2.length();

    if(n2 == 0)     // Base Case 1
        return true;

    if(n2 > n1)    // Base Case 2
        return false;

    for(int i = 0; i < s1.length(); i++)
        if(s1.charAt(i) == s2.charAt(0))        // if first char matches
            if(isRestMatch(i+1, s1, s2))       // check if rest match
                return true;

    return false;
}

static boolean isRestMatch(int start, String s1, String s2){
    int n = s2.length();
    for(int i = start, x = 1; i < n; i++, x++)
        if(s1.charAt(i) != s2.charAt(x))
            return false;

    return true;
}

Upvotes: 2

Bohemian
Bohemian

Reputation: 425073

Technically, this solves the problem:

public static void isSubstring(String subStr, String mainStr){
    return mainStr.matches(".*\\Q" + subStr + "\\E.*");
}

Upvotes: 1

ColOfAbRiX
ColOfAbRiX

Reputation: 1059

I've found this Java implementation

public String strStr(String haystack, String needle) {

    int needleLen = needle.length();
    int haystackLen = haystack.length();

    if (needleLen == haystackLen && needleLen == 0)
        return "";

    if (needleLen == 0)
        return haystack;

    for (int i = 0; i < haystackLen; i++) {
        // make sure in boundary of needle
        if (haystackLen - i + 1 < needleLen)
            return null;

        int k = i;
        int j = 0;

        while (j < needleLen && k < haystackLen && needle.charAt(j) == haystack.charAt(k)) {
            j++;
            k++;
            if (j == needleLen)
                return haystack.substring(i);
        }

    }

    return null;
}

Upvotes: 0

Related Questions