4
  public class StringIsSubstring {


public static void main(String[] args) {
    String s1= new String("anurag");
    String s2=new String("anu");

    char a[]=s1.toCharArray();
    char b[]=s2.toCharArray();
    int i=0;
    int j=0;

    while(i<a.length && j<b.length)
    {
        if(a[i]==b[j])
        {
            i++;
            j++;
        }
        else
        {
            i++;
            j=0;
        }
        if(j == b.length)
        {
            System.out.println("we have found the substring");
        }
    }
}
 }

I have written following code to find that one String is substring of other or not. I dont want to use any library function. Is there any more efficient way to do the same

3
  • 1
    Why String s1= new String("anurag"); instead of just String s1="anurag";? You can break the loop if j is greater than 0 and it's a no-match. Dec 10, 2011 at 7:17
  • Agreed, never use the constructor of strings and primitive wrapper classes.
    – Stephan
    Dec 10, 2011 at 8:54
  • 1
    This algorithm is not working correctly: it will not find "anu" in "aanurag"
    – user85421
    Dec 10, 2011 at 10:21

4 Answers 4

3

It is not possible to do any operations on a String without using a library function. Your code uses String.toCharArray, for example. And if you can use that, then you can also use String.indexOf and avoid reinventing the wheel.

People have suggested Boyer-Moore. This is a good choice if you are going to search a large body of text (in String instances or in some other representation). However, if you are only going to search a small chunk of text (as in your question), then the setup costs of Boyer-Moore mean that String.indexOf() will be faster. The same applies for other sophisticated algorithms.


So, the only way this question makes sense is if this is a homework exercise which includes a constraint on what you are allowed to use to solve the problem. In that case, unless you are doing an algorithmics course, I doubt that they expect you to research and implement a sophisticated algorithm.

1

Boyer-Moore has already been suggested, but let me also point out that your algorithm is actually broken. For example, if you want to test whether "coa" is a substring of "cocoa" (which is true), then you will match up to "co", then it will reset j on the next "c", but the problem is that now you have already "consumed" the "c" that starts the substring, and you don't get a match.

0

The previous comments have offered good reasons for applying a library function, however perhaps you are tasked with applying an alternate algorithm. From the sounds of your post, you are likely to be working with small s1s and s2s. For this purpose, the KnuthMorrisPratt algorithm yields good efficiency. You can implement this like so :

public class SOStringDemo {

    public static void main(String[] args) {

        SOStringIsSubstring pair = new SOStringIsSubstring();

        pair.text = "thequickbrownfoxanujumpedoverthelazydogs";
        pair.pattern = "anu";

        pair.KMPMatch();

        return;
    }
}

And the class file :

public class SOStringIsSubstring {

    public String text;
    public String pattern;
    private char[] textArray;
    private char[] patternArray;
    private int[] prefix;

    public void KMPMatch() {

        textArray = text.toCharArray();
        patternArray = pattern.toCharArray();
        int n = textArray.length;
        int m = patternArray.length;

        ComputePrefixFunction();
        int q = 0;

        for(int i = 0; i < n; i++) {
            while((q > 0) && (patternArray[q]) != textArray[i])
                q = prefix[q];
            if(patternArray[q] == textArray[i])
                ++q;
            if(q == m) {
                System.out.println("SubString is at index " + (i - m + 2));
                q = prefix[q-1];
            }
        }

        return;
    }

    public void ComputePrefixFunction() {

        int m = patternArray.length;
        prefix = new int [m];
        int k = 0;
        for(int q = 1; q < m; q++) {
            while((k > 0) && (patternArray[k] != patternArray[q]))
                k = prefix[k-1];
            if(patternArray[k] == patternArray[q])
                ++k;
            prefix[q] = k;
        }

        return;
    }
}
0

You can see Boyer-Moore algorithm http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm and http://en.wikipedia.org/wiki/String_searching_algorithm . You can see also String.indexOf java implementation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.