Find substring count without string functions

Question

Find the substring count from a string without string functions in Java. Given String str = "abcdefghcde"; and String find = "cde";, count occurrences of "cde" in String str.

Taking into account overlaps.

Example: String str = "cdcdcdc"; and String find = "cdc";, occurrence count is 3

Please give any feedback about improving it or any issues (performance or otherwise) that you see.

String input = "cdcdcdcdcdcddc";
    String find = "cdc";
    StringBuffer found = new StringBuffer();
    int count = 0;
    int j=0;
    for ( int i = 0; i <input.length();){
            j = 0;
            while(j<find.length() && i<input.length() && input.charAt(i) == find.charAt(j)) {
                found.append(input.charAt(i));
                j++;
                i++;
            }
            i=i-j;
            if(found.toString().equals(find)) {
                count++;
            }
            i++;
            found.setLength(0);
        }
    System.out.println("count is " + count);
    }

I have another question here which doesn't take into account overlaps and it's complexity is \$O(n)\$. But for this question, I'm unable to achieve \$O(n)\$ time running time.

Update: For all the people down voting, this is not a duplicate but a variant of the other question. If posting variants of a question is against the rules of stackexchange, please let me know and I'll delete my other post. Otherwise, I'd like to keep the other post because my solutions are slightly different in approach and much different in complexity and I'd like a feedback on both of them. Posting them as part of one post would be messy, both for me, and for the people trying to give feedback.

Answer 1

Efficiency

If you want to badly enough, I'm pretty sure you can improve the efficiency of your current code, at least for typical cases--but I don't think the result will be \$O(N)\$ even if you do.

For the moment, let's treat \$N\$ as the length of the string you're searching in (which I'm going to call the haystack), and \$M\$ as the length of the string you're searching for (which I'm going to call the needle).

As you've implemented it, this is an \$O(MN)\$ operation. That is, there are \$N\$ positions in the haystack where the needle could be found, and \$M\$ comparisons to verify whether you've found the needle at that location.

The obvious way to reduce the complexity would be to use something like a Boyer-Moore search. A full Boyer-Moore search is fairly tricky to get correct, but you could use (for example) Sunday's variant of Boyer-Moore-Horspool.

So, let's start by describing the basic idea of B-M searching. Unlike most string searching, B-M based searches start from the end of the needle. For example, let's assume I'm doing a search like:

Needle: abcde    
Haystack: abcabcdqwerpuiasdfasdfabcdeyakkfdabcdessity

Now, if there were a match at the first position in the haystack, the first characters would obviously have to be abcde. Using your method (starting from the beginning), we'd start from the beginning of the needle, and do four comparisons before we found that this wasn't a match (i.e., the a, b and c all matched, to it wasn't until we got to the next a that we knew it couldn't match.

With any of the Boyer-Moore variants, we'd start by looking at the fifth character in the haystack. We can't have a match at the first position unless that matches. It doesn't, so we can reject the first position with only one comparison.

Now, what we'd like to do next would be to jump ahead to the next position where a match is possible. We can look at the character there (a b, if I'm counting correctly). Looking at our needle, we know that only occurs at the second position, so we can jump ahead three more, and look at that character. That's a q, which doesn't occur in the needle, so we can jump ahead 5 more characters after that. Lather, rinse, repeat.

To manage that jumping, we don't want to scan through our needle every time to find where (of if) a character occurs in it. To avoid that, we build a table of character positions. The elements in the table will be the distance each character is from the end of the needle (and if the character doesn't occur in the needle, it'll be the length of needle + 1). That'll give us the location where we need to look for our next possible match.

When/if we get to a point where we've hit a zero in the table, we do a full comparison to see if we've found a location where the needle occurs.

abcabcdqwerpuiasdfasdfabcdeyakkfdabcdessity
abcde
   abcde
        abcde
             abcde
                  abcde
                     [abcde]

Now, there is a little bit of trickiness to deal with. This occurs if the needle contains the same character at two (or more) locations. For example, if the needle were literally needle, we have three locations where an e could indicate a match.

This is where the variants start to show up. The original Boyer-Moore built a rather complex 2D table with all those possible jumps encoded into it. The variants simplify that to at least some degree, gaining quite a bit in simplicity in exchange for a loss of efficiency (that's usually fairly minor).

In the variant I prefer, we (as pointed out above) only start to do a comparison when we reach a point where we've found a 0 in the shift table. In this case, we don't need a table of other locations where that occurs. We just need one secondary jump to the next possible match location for that one character. In this case, that would be 3 because it's three characters back from the last e to the second to last e in needle.

Looking at overall complexity, this can be a lot lower, especially if our needle is long and consists of unique characters. On the other hand, if it's short and consists entirely of repeated characters (e.g., cc) we're not going to gain much at all. At the same time, if the needle is short, the \$O(MN)\$ method is already close to the \$O(N)\$ we'd like. It's only when \$M\$ is large that the \$O(MN)\$ method becomes a serious problem--and that's exactly when a Boyer-Moore (or variant) search is most likely to give us the biggest gain (the primary exception being when/if the needle is long, but contains lots of repetition). Since big-O deals with the worst case, I think this is still \$O(MN)\$--but that only arises if the needle consists entirely of repetitions of a single character, and the haystack consists almost entirely of that same character as well. That's fairly degenerate (and probably unusual case, but to use @Coderodde's example, if you're searching for cc in cccc, all the work is mostly wasted, because you're going to do a full comparison at every candidate position in the haystack, so it still ends up as \$O(MN)\$.

Your code

Looking at your code, I'm most puzzled by your use of the found buffer. You're basically copying characters from the input to found as long as the two match, then checking the length of found to see if you've gotten a match.

Instead of that, I think I'd move the check for a match at the current position into a separate function, which would implement an algorithm on this general order:

for pos = 0 to needle.length()
    if (hay_stack[start_pos + pos] != needle[pos])
        return false
return true