使用swift语言实现了一下KMP算法，具体代码如下
详细的描述了KMP算法推导next数组的流程
//最初的next数组
func get_next(T: NSString) -> [Int] {
//由于Swift不支持字符串通过下标取字符所以使用NSString类型
/*
整个循环可以看做是字符串截取，假设进来的是字符串“abcaba”，
在循环前默认next数组的第一位回溯值，next[0]=0，由于字符串从下标0开始，所以后面回溯值减一作为区分
第一次循环满足j==-1的条件，结束时i==1、j==0、next=[0,1]
第二次循环截取"ab"，i是b的下标，j是a的下标，a!=b，所以进到else，j值回溯到-1，结束时i==1、j==-1、next=[0,1]
第三次循环满足j==-1，此时的操作是将i向后移一位，为下一次循环做铺垫，结束时i==2、j==0、next=[0,1,1]
第四次循环截取"abc"，i是c的下标，j是a的下标，a!=b，又进else，j值回溯-1，结束时i==2、j==-1、next=[0,1,1]
第五次循环与第三次相同，结束时i==3、j==0、next=[0,1,1,1]
第六次循环截取"abca"，i是第四个a的下标，j是第一个a的下标，a==a，满足条件，结束时i==4、j==1、next=[0,1,1,1,2]
第七次循环截取"abcab"，i是第五个b的下标，j是第二个b的下标，第一个a和第四个a比较过了是相同的，为了找出最大匹配字符串继续所以比较其后一位，同样b==b，满足条件，结束时i==5、j==2、next=[0,1,1,1,2,3]
第八次循环截取"abcaba"，i是第六个a的下标，j是c的下标，a!=c，进入else，j值回溯-1，结束时i==5、j==-1、next=[0,1,1,1,2,3]
第九次由于i==5不小于字符串长度，整个循环结束，最终字符串"abcaba"的next数组为[0,1,1,1,2,3]
*/
var i = 0 //当前“截取”的字符串的最后一个字符
var j = -1 //当前“截取”的字符串的第一个字符及帮助i值的后移操作
var next = [Int]()
next.append(0) //添加第一位回溯值
while (i < T.length-1) {
if (j == -1) || String(T.character(at: j)) == String(T.character(at: i)) {
i += 1
j += 1
next.append(j+1) //因为后面使用到next数组时需要取到对应的下标，所以保存时做了+1操作
} else {
j = next[j]-1 //由于判断值为-1
}
}
return next
}
改进后的next数组，修复了next数组在某些情况下存在的多余匹配，总体思路是将相同的字符使用同一回溯值。
func get_nextval(T: NSString) -> [Int] {
var i = 0 //当前“截取”的字符串的最后一个字符
var j = -1 //当前“截取”的字符串的第一个字符及帮助i值的后移操作
var nextval = [Int]()
nextval.append(0) //添加第一位回溯值
while (i < T.length-1) {
if (j == -1) || String(T.character(at: j)) == String(T.character(at: i)) {
i += 1
j += 1
//------------nextval与next的区别-----------
//判断如果当两个字符串相等，则使用较前的值作为回溯值
//例如字符串"abcad",当判断到第一个a和第四个a相同时，第四个a就使用和第一个a一样的回溯值0
//这样做的好处是可以避免子串与母串匹配失败后又重复匹配的问题
if String(T.character(at: j)) != String(T.character(at: i)) {
nextval.append(j+1) //如果不同则添加新的回溯值
} else {
nextval.append(nextval[j]) //添加较前的回溯值
}
//----------------------------------------
} else {
j = nextval[j]-1 //由于判断值为-1
}
}
return nextval
}
实现KMP算法，字符串的匹配流程
func index_KMP(S: NSString, T: NSString) -> Int {
var i = 0
var j = 0
var next = get_nextval(T: T)
while i < S.length && j+1 <= T.length {
if j == -1 || String(S.character(at: i)) == String(T.character(at: j)) {
i += 1
j += 1
} else {
j = next[j]-1 //子串回溯
}
}
//返回子串第一位在母串中的位置
return i-T.length
}
尝试调用
override func viewDidLoad() {
super.viewDidLoad()
print(get_next(T: "aaab"))
print(get_nextval(T: "aaab"))
print(index_KMP(S: "ababaaaba", T: "aaab"))
}
输出结果
[0, 1, 2, 3]
[0, 0, 0, 3]
4
