Find that one line is a substring of another or not

Question

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 wrote the following code to find if one line is a substring of another or not. I do not want to use any library function. Is there a more efficient way to do the same

Answer 1

It is not possible to perform any operations with String without using a library function. For example, your code uses String.toCharArray . And if you can use this, you can also use String.indexOf and avoid wheel reuse.

People suggested Boyer-Moore. This is a good choice if you intend to search for large text (in String instances or in another representation). However, if you are going to look for a small piece of text (as in your question), then the cost of installing Boyer-Moore means that String.indexOf() will be faster. The same applies to other complex algorithms.

---

So, the only way this question makes sense is that this is a homework exercise that includes a restriction on what you are allowed to use to solve the problem. In this case, if you do not complete the course of algorithms, I doubt that they expect you to study and implement a complex algorithm.

Answer 2

You can see the Boyer-Moore algorithm http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm and http://en.wikipedia.org/wiki/String_searching_algorithm . You can also see the implementation of the Java script String.indexOf.

Answer 3

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

Answer 4

The previous comments provided good reasons for using the library function, however, you may be instructed to use an alternative algorithm. From the sounds of your message, you are likely to work with small s1s and s2s. For this purpose, the KnuthMorrisPratt algorithm provides good performance. You can implement it like this:

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