Swift 实现KMP算法

使用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