字符串查找通常有四种方式，暴力查找，KMP查找，BoyerMoore查找以及RabinKarp算法查找，查找最简单的莫过于暴力查找，如果内容是“FlyElephant”，需要查找的内容是“Elephant”，上面的四种方式会给出不同的方案~

暴力查找

最简单的暴力查找:

+(BOOL)simpleMatchPattern:(NSString *)text pattern:(NSString *)pattern{
   NSInteger cnlen=text.length;
   NSInteger ptlen=pattern.length;
   for (NSInteger i=0; i<=cnlen-ptlen; i++) {
       NSInteger j;
       for (j=0; j<ptlen; j++) {
           unichar tChar=[text characterAtIndex:i+j];
           unichar pChar=[pattern characterAtIndex:j];
           if (tChar!=pChar) {
               break;
           }
       }
       if (j==ptlen) {
           return YES;
       }
   }
   return NO;
}

遍历内容的长度，获取索引m，然后索引m...m+匹配长度，逐一比较，这个算法可以稍微改进一下：

+(NSInteger)simpleBackMatchPattern:(NSString *)text pattern:(NSString *)pattern{
   NSInteger i,j;
   NSInteger cnlen=text.length;
   NSInteger ptlen=pattern.length;
   for (i=0,j=0; i<cnlen && j<ptlen; i++) {
       unichar tChar=[text characterAtIndex:i];
       unichar pChar=[pattern characterAtIndex:j];
       if (tChar==pChar) {
           j++;
       }else{
           i=i-j;
           j=0;
       }
   }
   if (j==ptlen) {
       return i-ptlen;
   }else{
        return 0;
   }
}

KMP算法

KMP是knuth,Morris和Pratt发明的算法，暴力查找的每次只是循环是固定的加1，假设内容中只有A,B两种你字符，假设查找的字符串是BAAAABAAB，模式字符串为BAAB，我们发现前两个匹配，第三个不匹配，暴力中，我们的循环会从索引1开始继续比较，但是匹配我们知道其他的全是A，所以我们应该从第二个字母B开始匹配，减少回退的成本，实现代码:

static const NSInteger LetterCount=256;
@interface KMPSearch()

@property (strong,nonatomic) NSString *pattern;

@property (strong,nonatomic) NSMutableArray *dfa;

@end

@implementation KMPSearch

-(instancetype)initWithPattern:(NSString *)pattern{
   self=[super init];
   if (self) {
       self.pattern=pattern;
       [self setupData];
   }
   return self;
}

-(NSInteger)search:(NSString *)text{
   NSInteger i,j;
   NSInteger plen=self.pattern.length;
   NSInteger tlen=text.length;
   for (i=0,j=0; i<tlen & j<plen; i++) {
       unichar uc=[text characterAtIndex:i];
       NSArray *arr=self.dfa[uc];
       j=[arr[j] integerValue];
   }
   if (j==plen) {
       return i-plen;
   }else{
       return -1;
   }
}

-(void)setupData{
   NSInteger plen=self.pattern.length;

   self.dfa=[[NSMutableArray alloc]initWithCapacity:LetterCount];
   
   for (NSInteger i=0; i<LetterCount; i++) {
       NSMutableArray *arr=[[NSMutableArray alloc]init];
       for (NSInteger m=0; m<plen; m++) {
           [arr addObject:@(0)];
       }
       [self.dfa addObject:arr];
   }
   
   NSInteger index=[self.pattern characterAtIndex:0];
   self.dfa[index][0]=@(1);
   for (NSInteger X=0,j=1; j<plen;j++) {
       for (NSInteger c=0; c<LetterCount; c++) {
           self.dfa[c][j]=self.dfa[c][X];
       }
       NSInteger uc=[self.pattern characterAtIndex:j];
       self.dfa[uc][j]=@(j+1);
       X=[self.dfa[uc][X] integerValue];
   }
   
}

@end

BoyerMooer算法

之前的暴力查找和KMP都是从左向右扫描文本对比实现的，但是BoyerMoore是从右向组走扫描实现的,具体实现:

static const NSInteger LetterCount=256;

@interface BoyerMoore()

@property (strong,nonatomic) NSString *pattern;

@property (strong,nonatomic) NSMutableArray *rightArr;

@end

@implementation BoyerMoore

-(instancetype)initWithPattern:(NSString *)pattern{
   self=[super init];
   if (self) {
       self.pattern=pattern;
       [self setup];
   }
   return self;
}

-(NSInteger)search:(NSString *)text{
   NSInteger tlen=text.length;
   NSInteger plen=self.pattern.length;
   NSInteger skip;
   for (NSInteger i=0; i<=tlen-plen; i+=skip) {
       skip=0;
       for (NSInteger j=plen-1;j>=0;j=j-1) {
           if ([self.pattern characterAtIndex:j]!=[text characterAtIndex:(i+j)]) {
               NSInteger index=[text characterAtIndex:(i+j)];
               skip=j-[self.rightArr[index] integerValue];
               break;
           }
       }
       if (skip==0) {
           return i;//匹配成功
       }
   }
   return -1;//匹配失败
}

-(void)setup{
   self.rightArr=[[NSMutableArray alloc]init];
   for (NSInteger i=0; i<LetterCount; i++) {
       [self.rightArr addObject:@(-1)];
   }
   
   for (NSInteger j=0; j<self.pattern.length; j++) {
       NSInteger index=[self.pattern characterAtIndex:j];
       self.rightArr[index]=@(j);
   }
}

@end

Rabin-Karp指纹字符串查找

Rabin和Karp这种算法和前三种走了完全的不同的方向，基于散列的查找，也就是每一个字符串都有一个对应的Hash值，如果Hash值相同的话，那么匹配成功，基本效率保持在O(n).

static  const NSInteger Q=997;
static  const NSInteger LetterCount=10;
@interface RabinKarp()

@property (strong,nonatomic) NSString *pattern;

@property (assign,nonatomic) NSInteger pCount;
@property (assign,nonatomic) NSInteger RM;
@property (assign,nonatomic) NSInteger pathHash;

@end

@implementation RabinKarp

-(instancetype)initWithPattern:(NSString *)pattern{
   self=[super init];
   if (self) {
       self.pattern=pattern;
       self.pCount=self.pattern.length;
       [self setup];
   }
   return self;
}

-(NSInteger)search:(NSString *)text{
   NSInteger tlen=text.length;
   NSInteger txtHash=[self hash:text length:self.pCount];
   //开头匹配成功
   if (self.pathHash==txtHash) {
       return 0;
   }
   
   for (NSInteger j=self.pCount; j<tlen; j++) {
       //逐一匹配
       NSInteger chValue=[[text substringWithRange:NSMakeRange(j-self.pCount, 1)] integerValue];
       txtHash=(txtHash+Q-self.RM*chValue%Q)%Q;
       NSInteger num=[[text substringWithRange:NSMakeRange(j, 1)] integerValue];
       txtHash=(txtHash*LetterCount+num)%Q;
       if (self.pathHash==txtHash) {
           return j-self.pCount+1;
       }
   }
   return -1;
}

-(void)setup{
   self.RM=1;
   for (NSInteger i=1; i<=self.pCount-1; i++) {
       self.RM=(LetterCount*self.RM)%Q;
   }
   self.pathHash=[self hash:self.pattern length:self.pCount];
}

-(NSInteger)hash:(NSString *)key length:(NSInteger)len{
   NSInteger hash=0;
   for (NSInteger j=0; j<len; j++) {
       NSInteger chValue=[[key substringWithRange:NSMakeRange(j, 1)] integerValue];
       hash=(LetterCount*hash+chValue)%Q;
   }
   return hash;
}

-(NSInteger)hashStr:(NSString *)key length:(NSInteger)len{
   NSInteger hash=0;
   for (NSInteger j=0; j<len; j++) {
       NSInteger chValue=[key characterAtIndex:j];
       hash=(LetterCount*hash+chValue)%Q;
   }
   return hash;
}

@end

测试代码：

   //1.暴力查找
   NSString *text=@"She is a girl";
   NSString *pattern=@"girl";
   if ([SearchMatch simpleMatchPattern:text pattern:pattern]) {
       NSLog(@"%@ is contains %@",text,pattern);
   }else{
       NSLog(@"%@ is not contains %@",text,pattern);
   }
   //2.简单回退
   text=@"FlyElephant";
   pattern=@"Elem";
   NSInteger matchIndex=[SearchMatch simpleBackMatchPattern:text pattern:pattern];
   if (matchIndex>0) {
       NSLog(@"%@ contains %@ ,index %ld",text,pattern,matchIndex);
   }else{
       NSLog(@"%@ is not contains %@",text,pattern);
   }
   //3.KMP查找
   NSString *kmpText=@"BCBAABACAABABACAA";
   NSString *kmpPattern=@"ABABAC";
   kmpText=@"AAACCBBDEF";
   kmpPattern=@"A";
   KMPSearch *kmp=[[KMPSearch alloc]initWithPattern:kmpPattern];
   NSInteger result=[kmp search:kmpText];
   if (result>=0) {
       NSLog(@"%@ contains %@ ,Match Begin index:%ld",kmpText,kmpPattern,result);
   }else{
       NSLog(@"%@ not contains %@ ",kmpText,kmpPattern);
   }
   //4.BoyerMoore查找
   NSString *bmText=@"FlyElephant";
   NSString *bmPattern=@"Fly";
   BoyerMoore *bm=[[BoyerMoore alloc]initWithPattern:bmPattern];
   NSInteger bmResult=[bm search:bmText];
   if (bmResult>=0) {
       NSLog(@"%@ contains %@,Begin Index:%ld",bmText,bmPattern,bmResult);
   }else{
       NSLog(@"%@ not contains %@",bmText,bmPattern);
   }
   
   //5.RabinKarp 查找
   NSString *rmText=@"3141592653589793";
   NSString *rmPattern=@"26535";
   RabinKarp *rm=[[RabinKarp alloc]initWithPattern:rmPattern];
   NSInteger rmResult=[rm search:rmText];
   if (rmResult>=0) {
       NSLog(@"%@ contains %@,Begin Index:%ld",rmText,rmPattern,rmResult);
   }else{
       NSLog(@"%@ not contains %@",rmText,rmPattern);
   }

FlyElephant.png