Count Occurence of Needle String in Haystack String, most optimally?

Question

The Problem is simple Find "ABC" in "ABCDSGDABCSAGAABCCCCAAABAABC" without using String.split("ABC")

Here is the solution I propose, I'm looking for any solutions that might be better than this one.

public static void main(String[] args) {
 String haystack = "ABCDSGDABCSAGAABCCCCAAABAABC";
 String needle = "ABC";
 char [] needl = needle.toCharArray();
 int needleLen = needle.length();
 int found=0;
 char hay[] = haystack.toCharArray();
 int index =0;
 int chMatched =0;

 for (int i=0; i<hay.length; i++){

  if (index >= needleLen || chMatched==0)
   index=0;
  System.out.print("\nchar-->"+hay[i] + ", with->"+needl[index]);

  if(hay[i] == needl[index]){
   chMatched++;
   System.out.println(", matched");
  }else {
   chMatched=0;
   index=0;
   if(hay[i] == needl[index]){
    chMatched++;
    System.out.print("\nchar->"+hay[i] + ", with->"+needl[index]);
    System.out.print(", matched");
   }else
   continue;
  }

  if(chMatched == needleLen){
   found++;
   System.out.println("found. Total ->"+found);
  }
  index++;
 } 
 System.out.println("Result Found-->"+found);
 }

It took me a while creating this one. Can someone suggest a better solution (if any) P.S. Drop the sysouts if they look messy to you.

Answer 1

How about:

boolean found = haystack.indexOf("ABC") >= 0;

**Edit - The question asks for number of occurences, so here's a modified version of the above:

public static void main(String[] args)
{
    String needle = "ABC";
    String haystack = "ABCDSGDABCSAGAABCCCCAAABAABC";

    int numberOfOccurences = 0;
    int index = haystack.indexOf(needle);
    while (index != -1)
    {
        numberOfOccurences++;
        haystack = haystack.substring(index+needle.length());
        index = haystack.indexOf(needle);
    }

    System.out.println("" + numberOfOccurences);
}

Answer 2

What about considering regex, Pattern and Matcher classes? Check this tutorial

Answer 3

If you're looking for an algorithm, google for "Boyer-Moore". You can do this in sub-linear time.

edit to clarify and hopefully make all the purists happy: the time bound on Boyer-Moore is, formally speaking, linear. However the effective performance is often such that you do many fewer comparisons than you would with a simpler approach, and in particular you can often skip through the "haystack" string without having to check each character.

Answer 4

You say your challenge is to find ABC within a string. If all you need is to know if ABC exists within the string, a simple indexOf() test will suffice.

If you need to know the number of occurrences, as your posted code tries to find, a simple approach would be to use a regex:

public static int countOccurrences(string haystack, string regexToFind) {
   Pattern p = Pattern.compile(regexToFind);
   Matcher m = p.matcher(haystack); // get a matcher object
   int count = 0;
   while(m.find()) {
       count++;
   }
   return count;
}

Answer 5

Asked by others, better in what sense? A regexp based solution will be the most concise and readable (:-) ). Boyer-Moore (http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm) will be the most efficient in terms of time (O(N)).

Answer 6

If you don't mind implementing a new datastructure as replacement for strings, have a look at Tries: http://c2.com/cgi/wiki?StringTrie or http://en.wikipedia.org/wiki/Trie

If you don't look for a regular expression but an exact match they should provide the fastest solution (proportional to length of search string).

Answer 7

Have a look at http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm