概述:本文主要講解KMP實現(xiàn)字符串快速查找的一個Demo;不了解KMP的同學(xué)可以參考:
KMP(一) 模式匹配算法推導(dǎo) --《部分匹配表》
KMP(二) 模式匹配算法實現(xiàn)
KMP(三) 字符串快速匹配示例
字符串快速匹配Demo下載
一. 目的效果:
QQ20170905-155723-HD.gif
對,就是這樣一個類似于網(wǎng)頁檢索的效果;實現(xiàn)起來也比較簡單;
Talk is cheap ,Show me your code!
二. 單純KMP的缺陷:
先來溫習(xí)下KMP(二) 模式匹配算法實現(xiàn)當(dāng)中的實現(xiàn)方案:
#pragma mark - getNext
-(NSArray<NSNumber *> *)getNextWithString:(NSString *)string{
NSMutableArray<NSNumber *> * next = [NSMutableArray arrayWithCapacity:string.length];
next[0] = @(-1);//初始化
int j= 0,k= -1; //j:記錄當(dāng)前下標(biāo); k記錄當(dāng)前位的next
while (j < string.length - 1) {
if (k== -1 || [string characterAtIndex:j] == [string characterAtIndex:k]) { // 比較當(dāng)前(j)字符與當(dāng)期位next處字符是否相等
next[++j] = @(++k); // 移動下標(biāo),并求解下一位的next;
}else{
k = [next[k] intValue]; // 回溯當(dāng)前位的next
}
}
return next;
}
-(NSArray<NSString *> *)indexKMPwithParentString:(NSString *)pString andSubstring:(NSString *)sString{
NSArray *next = [self getNextWithString:sString]; // 計算next數(shù)組
int index_s = 0 ,index_p = 0; //標(biāo)記 pString 和 sString 的當(dāng)前比對位置
NSMutableArray<NSString *> *ranges = [NSMutableArray array]; //用于保存匹配結(jié)果的range位置
while ((index_p < pString.length) && (index_s < sString.length)) { // 一直比對至兩個字符串結(jié)尾
if ([pString characterAtIndex:index_p] == [sString characterAtIndex:index_s]) { // 當(dāng)前比對位置的字符相等,則移動P和S繼續(xù)下一位比對
if ((index_s == sString.length - 1) && (index_p != pString.length -1)) { // 字串S比對至末尾,但是主串P未到末尾,即是說字串匹配成功,但是尚需確定主串的后續(xù)位置是否能匹配,故繼續(xù)比對
index_s = 0; //將字串S當(dāng)前比對位置移至起始位置
[ranges addObject:NSStringFromRange(NSMakeRange(index_p - sString.length + 1 , sString.length))]; //保存本次匹配的位置結(jié)果
continue; // 完成一次匹配,跳出本次循環(huán) index_p 不再移動
}
index_p ++; // 向后移動P的當(dāng)前位置
index_s ++; // 向后移動S的當(dāng)前位置
}else{ //當(dāng)前比對位置的字符不相等,則保持主串P位置不回溯,根據(jù)next數(shù)組回溯字串S
if (index_s != 0) { //特別處理 next[0] = "-1"的情況
index_s = [next[index_s] intValue]; // 根據(jù)next回溯當(dāng)前字串S的比對位置
}else{
index_p ++; //如果起始位置不匹配,則直接移動主串P
}
}
}
return ranges;
}
當(dāng)目標(biāo)子串僅有一個字符時候,顯然-(NSArray<NSString *> *)indexKMPwithParentString: andSubstring:方法存在缺陷,效率低于樸素查找方法;So,我們要做下改進,當(dāng)字串僅有一個字符時,采用樸素算法,當(dāng)然,也順便對上節(jié)中的代碼稍加整理規(guī)范;
三.字符串快速匹配完整實現(xiàn):
-
首先制作UI界面,一個Label一個TextField 就略過了,給TextField添加一個監(jiān)聽:
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(textFieldTextDidChangeNotification) name:UITextFieldTextDidChangeNotification object:nil];
-
實現(xiàn)TextFieldTextDidChangeNotification方法:
#pragma mark - UITextFieldTextDidChangeNotification,AttributedString相關(guān)
-(void)textFieldTextDidChangeNotification{
// 重置字體背景色
[_attString setAttributes:@{NSBackgroundColorAttributeName:[UIColor whiteColor]} range:NSMakeRange(0, _label.text.length)];
_label.attributedText = _attString;
_ranges = [self indexKMPwithParentString:_label.text andSubstring:_tf.text];
// 標(biāo)記匹配的字體背景色
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) { //檢索目標(biāo)字符串為多個字符
ranges = [[self indexKMPwithParentString:pString andMultipleChar:sString] copy];
}else{ //檢索目標(biāo)字符串為單個字符
ranges = [[self indexKMPwithParentString:pString andSingleChar:sString] copy];
}
return ranges;
}
-
next數(shù)組的計算:
#pragma mark - getNext
-(NSArray<NSNumber *> *)getNextWithString:(NSString *)string{
NSMutableArray<NSNumber *> * next = [NSMutableArray arrayWithCapacity:string.length];
next[0] = @(-1);//初始化
int j= 0,k= -1; //j:記錄當(dāng)前下標(biāo); k記錄當(dāng)前位的next
while (j < string.length - 1) {
if (k== -1 || [string characterAtIndex:j] == [string characterAtIndex:k]) { // 比較當(dāng)前(j)字符與當(dāng)期位next處字符是否相等
next[++j] = @(++k); // 移動下標(biāo),并求解下一位的next;
}else{
k = [next[k] intValue]; // 回溯當(dāng)前位的next
}
}
return next;
}
-
檢索匹配的實現(xiàn):
- 用于字串不是單個字符的情況,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數(shù)組
int index_s = 0 ,index_p = 0; //標(biāo)記 pString 和 sString 的當(dāng)前比對位置
NSMutableArray<NSString *> *ranges = [NSMutableArray array]; //用于保存匹配結(jié)果的range位置
while ((index_p < pLength) && (index_s < sLength)) { // 一直比對至兩個字符串結(jié)尾
if ([pString characterAtIndex:index_p] == [sString characterAtIndex:index_s]) { // 當(dāng)前比對位置的字符相等,則移動P和S繼續(xù)下一位比對
if ((index_s == sLength - 1) && (index_p != pLength -1)) { // 字串S比對至末尾,但是主串P未到末尾,即是說字串匹配成功,但是尚需確定主串的后續(xù)位置是否能匹配,故繼續(xù)比對
index_s = 0; //將字串S當(dāng)前比對位置移至起始位置
[ranges addObject:NSStringFromRange(NSMakeRange(index_p - sString.length + 1 , sString.length))]; //保存本次匹配的位置結(jié)果
continue; // 完成一次匹配,跳出本次循環(huán) index_p 不再移動
}
index_p ++; // 向后移動P的當(dāng)前位置
index_s ++; // 向后移動S的當(dāng)前位置
}else{ //當(dāng)前比對位置的字符不相等,則保持主串P位置不回溯,根據(jù)next數(shù)組回溯字串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;
}
代碼中用了大量的循環(huán),應(yīng)當(dāng)注意兩點:
1.不必要的計算不要引入循環(huán)體內(nèi);
2.實際應(yīng)用中可考慮開辟子線程;
