Counting occurrences of substring in string

Question

I need to know how many times a substring occurs in a given string. I figured that I might as well create an extension method:

public static int Occurences(this string str, string val)
{
 string copy = str;
 int instancesOf = 0;
 int indexOfVal;
 while ((indexOfVal = copy.IndexOf(val)) != -1)
 {
 copy = copy.Remove(indexOfVal, val.Count());
 instancesOf++;
 }
 return instancesOf;
}

I'm not sure that the assignment in the while loop is good practice. Should I change this to compute the value once outside the loop, and once in the loop, like this?

int indexOfVal = copy.IndexOf(val);
while (indexOfVal != -1)
{
 copy = copy.Remove(indexOfVal, val.Count());
 instancesOf++;
 indexOfVal = copy.IndexOf(val);
}

Any and all comments appreciated, the more the better.

• mjolka: Do you want to find overlapping instances? "bbb".Occurences("bb") returns 1.
• user34073: @mjolka That might be nice, but is not necessary.
• nhgrif: @Hosch250 You need to document expected behavior. Should "bbb".Occurrences("bb") return 1 or 2?
• user34073: Either will be fine, but I might as well have it return 2 for the sake of a thorough implementation.
• 200_success: If your val is long, and your str is pathological, the running time could be O(n^2). To avoid that, you could use a smarter string-searching algorithm, such as the Z Algorithm, which works in O(n) time.

Answer 1

Your current implementation could be more efficient. Copying the passed in string and chopping it up is probably pretty expensive (I'm not a master of .NET internals though).

val.Count()

Why not val.Length? Count() is very inefficient compared to Length.

copy = copy.Remove(indexOfVal, val.Count());

We don't need to remove part of the string, just search again starting at indexOfVal + val.Length.

Here is an example using an overload of String.IndexOf:

public static int Occurences(this string str, string val)
{ 
 int occurrences = 0;
 int startingIndex = 0;
 while ((startingIndex = str.IndexOf(val, startingIndex)) >= 0) 
 {
 ++occurrences;
 ++startingIndex;
 }
 return occurrences;
}

This implementation will count overlapping occurrences (so "bbb".Occurences("bb") will return 2.

If you don't want to count overlapping occurences, you can replace ++startingIndex; with:

startingIndex += val.Length

---

On why an exception isn't thrown in the case of "foo".Occurrences("o"), from MSDN:

If startIndex equals the length of the string instance, the method returns -1.

• user34073: Calling .IndexOf() with a startingIndex greater than the length of the string crashes, but it actually works in this statement because the assignment fails.
• craftworkgames: "probably pretty expensive" and "very inefficient" are not terms I would use to describe Count() and splitting strings. These are micro-optimizations and most of the time won't make a licking difference. Almost certainly, the implementation of Count() just returns Length for a string.
• nhgrif: @craftworkgames It's a community wiki answer. You're welcome to improve it as you see fit.
• user34073: @craftworkgames Probably true, but using .Length is probably the more correct version, and my code needs to be fast as it will be running on mobile devices as well as desktops.
• craftworkgames: Knowing different ways to code something is great. That's what code reviews are all about. It's just that "The biggest problems with 'premature optimization' are that it can introduce unexpected bugs and can be a huge time waster." programmers.stackexchange.com/questions/80084/…