Number of occurrences of a substring in an NSString?

How can I get the number of times an NSString (for example, @"cake") appears in a larger NSString (for example, @"Cheesecake, apple cake, and cherry pie")?

I need to do this on a lot of strings, so whatever method I use would need to be relatively fast.

Thanks!

Solution 1:

This isn't tested, but should be a good start.

NSUInteger count = 0, length = [str length];
NSRange range = NSMakeRange(0, length); 
while(range.location != NSNotFound)
{
  range = [str rangeOfString: @"cake" options:0 range:range];
  if(range.location != NSNotFound)
  {
    range = NSMakeRange(range.location + range.length, length - (range.location + range.length));
    count++; 
  }
}

Solution 2:

A regex like the one below should do the job without a loop interaction...

Edited

NSString *string = @"Lots of cakes, with a piece of cake.";
NSError *error = NULL;
NSRegularExpression *regex = [NSRegularExpression regularExpressionWithPattern:@"cake" options:NSRegularExpressionCaseInsensitive error:&error];
NSUInteger numberOfMatches = [regex numberOfMatchesInString:string options:0 range:NSMakeRange(0, [string length])];
NSLog(@"Found %i",numberOfMatches);

Only available on iOS 4.x and superiors.

Solution 3:

was searching for a better method then mine but here's another example:

NSString *find = @"cake";
NSString *text = @"Cheesecake, apple cake, and cherry pie";

NSInteger strCount = [text length] - [[text stringByReplacingOccurrencesOfString:find withString:@""] length];
strCount /= [find length];

I would like to know which one is more effective.

And I made an NSString category for better usage:

// NSString+CountString.m

@interface NSString (CountString)
- (NSInteger)countOccurencesOfString:(NSString*)searchString;
@end

@implementation NSString (CountString)
- (NSInteger)countOccurencesOfString:(NSString*)searchString {
    NSInteger strCount = [self length] - [[self stringByReplacingOccurrencesOfString:searchString withString:@""] length];
    return strCount / [searchString length];
}
@end

simply call it by:

[text countOccurencesOfString:find];

Optional: you can modify it to search case insensitive by defining options:

Solution 4:

There are a couple ways you could do it. You could iteratively call rangeOfString:options:range:, or you could do something like:

NSArray * portions = [aString componentsSeparatedByString:@"cake"];
NSUInteger cakeCount = [portions count] - 1;

EDIT I was thinking about this question again and I wrote a linear-time algorithm to do the searching (linear to the length of the haystack string):

+ (NSUInteger) numberOfOccurrencesOfString:(NSString *)needle inString:(NSString *)haystack {
    const char * rawNeedle = [needle UTF8String];
    NSUInteger needleLength = strlen(rawNeedle);

    const char * rawHaystack = [haystack UTF8String];
    NSUInteger haystackLength = strlen(rawHaystack);

    NSUInteger needleCount = 0;
    NSUInteger needleIndex = 0;
    for (NSUInteger index = 0; index < haystackLength; ++index) {
        const char thisCharacter = rawHaystack[index];
        if (thisCharacter != rawNeedle[needleIndex]) {
            needleIndex = 0; //they don't match; reset the needle index
        }

        //resetting the needle might be the beginning of another match
        if (thisCharacter == rawNeedle[needleIndex]) {
            needleIndex++; //char match
            if (needleIndex >= needleLength) {
                needleCount++; //we completed finding the needle
                needleIndex = 0;
            }
        }
    }

    return needleCount;
}