概述:本文主要讲解KMP实现字符串快速查找的一个Demo;不了解KMP的同学可以参考:
KMP(一) 模式匹配算法推导 --《部分匹配表》
KMP(二) 模式匹配算法实现
KMP(三) 字符串快速匹配示例
字符串快速匹配Demo下载
一. 目的效果:
QQ20170905-155723-HD.gif
对,就是这样一个类似于网页检索的效果;实现起来也比较简单;
Talk is cheap ,Show me your code!
二. 单纯KMP的缺陷:
先来温习下KMP(二) 模式匹配算法实现当中的实现方案:
#pragma mark - getNext
-(NSArray<NSNumber *> *)getNextWithString:(NSString *)string{
NSMutableArray<NSNumber *> * next = [NSMutableArray arrayWithCapacity:string.length];
next[0] = @(-1);//初始化
int j= 0,k= -1; //j:记录当前下标; k记录当前位的next
while (j < string.length - 1) {
if (k== -1 || [string characterAtIndex:j] == [string characterAtIndex:k]) { // 比较当前(j)字符与当期位next处字符是否相等
next[++j] = @(++k); // 移动下标,并求解下一位的next;
}else{
k = [next[k] intValue]; // 回溯当前位的next
}
}
return next;
}
-(NSArray<NSString *> *)indexKMPwithParentString:(NSString *)pString andSubstring:(NSString *)sString{
NSArray *next = [self getNextWithString:sString]; // 计算next数组
int index_s = 0 ,index_p = 0; //标记 pString 和 sString 的当前比对位置
NSMutableArray<NSString *> *ranges = [NSMutableArray array]; //用于保存匹配结果的range位置
while ((index_p < pString.length) && (index_s < sString.length)) { // 一直比对至两个字符串结尾
if ([pString characterAtIndex:index_p] == [sString characterAtIndex:index_s]) { // 当前比对位置的字符相等,则移动P和S继续下一位比对
if ((index_s == sString.length - 1) && (index_p != pString.length -1)) { // 字串S比对至末尾,但是主串P未到末尾,即是说字串匹配成功,但是尚需确定主串的后续位置是否能匹配,故继续比对
index_s = 0; //将字串S当前比对位置移至起始位置
[ranges addObject:NSStringFromRange(NSMakeRange(index_p - sString.length + 1 , sString.length))]; //保存本次匹配的位置结果
continue; // 完成一次匹配,跳出本次循环 index_p 不再移动
}
index_p ++; // 向后移动P的当前位置
index_s ++; // 向后移动S的当前位置
}else{ //当前比对位置的字符不相等,则保持主串P位置不回溯,根据next数组回溯字串S
if (index_s != 0) { //特别处理 next[0] = "-1"的情况
index_s = [next[index_s] intValue]; // 根据next回溯当前字串S的比对位置
}else{
index_p ++; //如果起始位置不匹配,则直接移动主串P
}
}
}
return ranges;
}
当目标子串仅有一个字符时候,显然-(NSArray<NSString *> *)indexKMPwithParentString: andSubstring:方法存在缺陷,效率低于朴素查找方法;So,我们要做下改进,当字串仅有一个字符时,采用朴素算法,当然,也顺便对上节中的代码稍加整理规范;
三.字符串快速匹配完整实现:
-
首先制作UI界面,一个Label一个TextField 就略过了,给TextField添加一个监听:
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(textFieldTextDidChangeNotification) name:UITextFieldTextDidChangeNotification object:nil];
-
实现TextFieldTextDidChangeNotification方法:
#pragma mark - UITextFieldTextDidChangeNotification,AttributedString相关
-(void)textFieldTextDidChangeNotification{
// 重置字体背景色
[_attString setAttributes:@{NSBackgroundColorAttributeName:[UIColor whiteColor]} range:NSMakeRange(0, _label.text.length)];
_label.attributedText = _attString;
_ranges = [self indexKMPwithParentString:_label.text andSubstring:_tf.text];
// 标记匹配的字体背景色
if (_ranges) {
for (NSString *string in _ranges) {
[_attString setAttributes:@{NSBackgroundColorAttributeName:[UIColor yellowColor]} range:NSRangeFromString(string)];
_label.attributedText = _attString;
}
}
}
#pragma mark - indexKMP
-(NSArray<NSString *> * _Nullable)indexKMPwithParentString:(NSString *)pString andSubstring:(NSString *)sString{
NSArray<NSString *> *ranges = [NSArray array];
if (sString.length > 1) { //检索目标字符串为多个字符
ranges = [[self indexKMPwithParentString:pString andMultipleChar:sString] copy];
}else{ //检索目标字符串为单个字符
ranges = [[self indexKMPwithParentString:pString andSingleChar:sString] copy];
}
return ranges;
}
-
next数组的计算:
#pragma mark - getNext
-(NSArray<NSNumber *> *)getNextWithString:(NSString *)string{
NSMutableArray<NSNumber *> * next = [NSMutableArray arrayWithCapacity:string.length];
next[0] = @(-1);//初始化
int j= 0,k= -1; //j:记录当前下标; k记录当前位的next
while (j < string.length - 1) {
if (k== -1 || [string characterAtIndex:j] == [string characterAtIndex:k]) { // 比较当前(j)字符与当期位next处字符是否相等
next[++j] = @(++k); // 移动下标,并求解下一位的next;
}else{
k = [next[k] intValue]; // 回溯当前位的next
}
}
return next;
}
-
检索匹配的实现:
- 用于字串不是单个字符的情况,KMP
#pragma mark - 用于字串不是单个字符的情况
-(NSArray<NSString *> * _Nullable)indexKMPwithParentString:(NSString *)pString andMultipleChar:(NSString *)sString{
NSUInteger sLength = sString.length;
NSUInteger pLength = pString.length;
if (sLength < 2 || pLength == 0) return nil;
NSArray *next = [self getNextWithString:sString]; // 计算next数组
int index_s = 0 ,index_p = 0; //标记 pString 和 sString 的当前比对位置
NSMutableArray<NSString *> *ranges = [NSMutableArray array]; //用于保存匹配结果的range位置
while ((index_p < pLength) && (index_s < sLength)) { // 一直比对至两个字符串结尾
if ([pString characterAtIndex:index_p] == [sString characterAtIndex:index_s]) { // 当前比对位置的字符相等,则移动P和S继续下一位比对
if ((index_s == sLength - 1) && (index_p != pLength -1)) { // 字串S比对至末尾,但是主串P未到末尾,即是说字串匹配成功,但是尚需确定主串的后续位置是否能匹配,故继续比对
index_s = 0; //将字串S当前比对位置移至起始位置
[ranges addObject:NSStringFromRange(NSMakeRange(index_p - sString.length + 1 , sString.length))]; //保存本次匹配的位置结果
continue; // 完成一次匹配,跳出本次循环 index_p 不再移动
}
index_p ++; // 向后移动P的当前位置
index_s ++; // 向后移动S的当前位置
}else{ //当前比对位置的字符不相等,则保持主串P位置不回溯,根据next数组回溯字串S
if (index_s != 0) { //特别处理 next[0] = "-1"的情况
index_s = [next[index_s] intValue];
}else{
index_p ++;
}
}
}
return ranges.count ? ranges:nil;
}
2.用于字串是单个字符的情况,采用朴素匹配效率更高
-(NSArray<NSString *> * _Nullable )indexKMPwithParentString:(NSString *)pString andSingleChar:(NSString *)singleChar{
if (singleChar.length == 0 || pString.length == 0) return nil;
int i = 0;
NSMutableArray<NSString *>* ranges = [NSMutableArray array];
unichar singchar = [singleChar characterAtIndex:0];
while (i < pString.length) {
if (singchar == [pString characterAtIndex:i]) {
[ranges addObject: NSStringFromRange(NSMakeRange(i, 1))];
}
i ++;
}
return ranges.count ? ranges:nil;
}
代码中用了大量的循环,应当注意两点:
1.不必要的计算不要引入循环体内;
2.实际应用中可考虑开辟子线程;
