在正式开始之前，我们先来做一个简单的算法题。请从大字符串bigString = @"goodgoogle"中，找到小字符串smallString = @"google"的位置。
一般来说，我们会有以下的思路：
1、从bigString的第一位开始比较，如果匹配成功，继续下去。闪电表示不相等
44D93D49-815D-4F05-8981-9813D80F9CB5.png
2、在主串的第五个字符不相等，这个时候，我们就开始从主串的第二个字符开始往后比较
1550A0C4-421F-4579-91E4-72B2F7EA84A6.png
3、如果不相等，一直重复第二个步骤，知道主串结束
283C51EC-7B32-4B12-A7E5-37966F18C620.png
这里我们看到第五个的时候，找到了子串的位置。
这个实现的思路就是：对主串的每一个字符串作为子串的开头进行比较，对主串做大循环，直到完全匹配成功，获取全部遍历结束为止。
实现代码：
- (void)FirstAlgorithm{
NSString *bigString = @"goodgoogle";
NSString *smallString = @"google";
BOOL ret = YES;
NSInteger count = 0;//记录执行次数
NSInteger i = 0;//长串
NSInteger j = 0;//短串
while (ret) {
char a = [bigString characterAtIndex:i];
char b = [smallString characterAtIndex:j];
if (i < bigString.length-1 && j < smallString.length-1) {
//保证i和j分别小于他们字符串的长度
if (a == b) {
//当a=b的时候，i和j分别都加1
j += 1;
i += 1;
}else{
//当不相等的时候，j继续从0开始，而i从上一次的下一位开始
i = i - j + 1;
j = 0;
}
}else{
ret = NO;
}
count += 1;
}
NSLog(@"计算次数：%ld",count);
NSLog(@"第：%ld 个相等",j);
}
这个算法时间复杂度为O(m+n),m为主串的长度，n为子串的长度
我们观察上面匹配过程发现，其实在第一次匹配失败以后，第二次匹配根本没有必要从主串的第二位开始比较了。因为子串的第一个字符和第四个字符相等，所以，子串的的第一个字符肯定不会跟主串的2、3、4位字符相等了，最少会跟主串的第五位相等，所以我们做了好几步重复操作。这是我们可以引入我们的主题了KMP模式匹配算法
KMP模式匹配算法
在很多年前的科学家认为，像这种拥有重复字符的字符串，挨个的遍历，是一个很消耗性能的事情，于是三位前辈D.E.knuth J.H.Morris V.R.Pratt共同发表了一个模式匹配算法，可以大大的避免重复遍历的情况，我们称之为克努特-莫里斯-普拉特算法，简称KMP模式匹配算法
俗话说：没有对比就没有伤害，但是我们要理解KMP模式匹配算法我们还必须要跟普通匹配算法比较一下，这样我们才能理解KMP模式匹配算法的逻辑
逻辑1
假设主串S=@"abcdefgab",字串T=@"abcdex"我们进行比较
普通匹配算法
1117D4E4-3E20-43DC-BCB6-66C5EB7FD431.png
而根据我们的KMP算法，我们其实是可以直接从第六个字符开始比较的，也就是这两步
312FD903-95DC-489B-912E-D86722D84B80.png
312FD903-95DC-489B-91
逻辑2
这时候有人也许会问，如果T串后面也有a该怎么处理，这个时候我们就需要进行进一步的判断了。
假设主串S=@"abcdefgab",字串T=@"abcaex"
39A28D0B-58E6-449A-8FF0-090CDA6A403D.png
因为T的首位a和T的第四位a相等，第二位b和第五位b相等。而在第一步时，第四位a和第五位b已经与主串S中相应的位置比较过了，是相等的。所以，我们是可以直接进行这样比较的
22BA1128-1C1F-438D-BFEF-78AE8F81FF9C.png
我们KMP算法就是为了不回溯，所以我们的i就不要变小了，我们就只考虑j值得变化，而j值得变化其实与主串无关，只与子串有关。j值得大小取决于子串内部结构是否与之前有重复。
我们把T串各个位置的j值得变化定义一个数组next,数组next的长度就是T串的长度。
next[i]（i从1开始算）代表着，除去第i个数，在一个字符串里面从第一个数到第（i-1）字符串前缀与后缀最长重复的个数。
什么是前缀？
在“aba”中，前缀就是“ab”，除去最后一个字符的剩余字符串。
同理可以理解后缀。除去第一个字符的后面全部的字符串
在“aba”中，前缀是“ab”，后缀是“ba”，那么两者最长的子串就是“a”；
在“ababa”中，前缀是“abab”，后缀是“baba”，二者最长重复子串是“aba”；
在“abcabcdabc”中，前缀是“abcabcdab”，后缀是“bcabcdabc”，二者最长重复的子串是“abc”；
next数组的推导
1、T=“abcdex”
- 1、当j=1时 ，next[1]=0
- 2、当j=2时，j由1到j-1就只有字符a，没有与其他相同的字符,next[2]=1
- 3、j=3，j由1到j-1就有字符ab，没有相同的，next[3]=1
以后同理
next数组为[0,1,1,1,1]
2、T=“abcabx”
- 1、当j从1到4时，同第一个例子，都是1
- 2、当j=5时，j由1到j-1的字符串是
abca,前缀字符a和后缀字符a相等，所以 next[5]=2 - 3、当j=6时，j由1到j-1的字符串是
abcab,前缀字符ab和后缀字符ab相等，所以 next[5]=3
next数组为[0,1,1,2,3]
我们根据经验得到如果前后缀一个字符相等，k值是2，如果两个值相等k是3，n个相等k值是n+1
我的next算法代码
///获取next数组
- (NSArray*)get_NextWithText:(NSString *)text{
NSMutableArray *next = [NSMutableArray new];
//第一步，先把next 里面内容都设置为0
for (int i = 0; i < text.length; i++) {
[next addObject:@0];
}
for (int i = 1; i < text.length; i++) {
///小串
NSString *smallStr = [text substringToIndex:i];
//记录最大重复值
NSUInteger T = 0;
for (NSUInteger j = smallStr.length-1; j > 0; j--) {
//前缀
NSString *prefix = [smallStr substringToIndex:j];
if ([smallStr hasSuffix:prefix] && j > T) {
T = j;
}
}
next[i] = @(T+1);
}
return next;
}
网上有很多种不同形式的算法，我这里的思想是，首先找出前缀,然后根据hasSuffix判断前缀和后缀是否相同，但是我们在判断的时候，需要先考虑前缀最大的情况，然后依次减小，而不是由小到大。
KMP代码
///第二种算法KMP
- (void)SecondAlgorithm{
NSString *bigString = @"goodgoogle";
NSString *smallString = @"google";
BOOL ret = YES;
NSInteger count = 0;//记录执行次数
NSInteger i = 0;//长串
NSInteger j = 0;//短串
NSArray *nextList = [self get_NextWithText:smallString];
while (ret) {
char a = [bigString characterAtIndex:i];
char b = [smallString characterAtIndex:j];
if (i < bigString.length-1 && j < smallString.length-1) {
//保证i和j分别小于他们字符串的长度
if (a == b) {
//当a=b的时候，i和j分别都加1
j += 1;
i += 1;
}else{
//当不相等的时候，i继续增加，但是j是nextList[j]，而不是从0开始了
i += 1;
j = [nextList[j] integerValue];
}
}else{
ret = NO;
}
count += 1;
}
NSLog(@"计算次数：%ld",count);
NSLog(@"第：%ld 个相等",j);
}
主要思想是：在当两个字符不相等的时候，小串的j不要在总0开始了，要从next数组里面相应的值开始
打印结果
BB8970C5-E7C5-4BAA-95F6-A3FAD1DCAC69.png
这两个字符串减少了三次运算
网友评论