kmp算法

Go 解法, 执行用时: 3ms, 内存消耗: 1264KB, 提交时间: 2021-06-28

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
*/
func kmp( S string ,  T string ) int {
    m  := len(S)
    n := len(T)
    next := getnext(S)
    ret := 0
    for i,j :=0,0;i<n; {
        if j==-1 || S[j]==T[i]  {
            i++
            j++
        } else {
            j=next[j]
        }
        if j==m {
            j=next[j]
            ret++
        }
    }
    return ret
    // write code here
}

func getnext( s string ) []int{
    strlon :=len(s)
    var next []int
    next=make([]int, strlon+1)
    j :=-1
    i :=0
    next[0]=-1
    for i<strlon {
        if j==-1 || s[j]==s[i]{
            i++
            j++
            next[i]=j
        }   else {
            j=next[j]
        }
        
    }
    return next   
}

Go 解法, 执行用时: 3ms, 内存消耗: 1332KB, 提交时间: 2021-04-03

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
*/
func kmp( S string ,  T string ) int {
    // write code here
    //构造状态机next
    next := GetNext(S)
    //计算出现次数
    result := handle(T, S, next)
 
    return result
}

func handle(s, p string,next []int) int {
    //p是pattern待匹配的字符串
    i,j := 0,0
    result := 0
    for i < len(s) {
        if j == -1 || s[i] == p[j]{
            j++
            i++
        }else{
            //不同的话根据状态机，看回退到哪个位置
            j = next[j]
        }
 
        if j >= len(p) {
            //j已经达到了匹配字符串的长度，那么出现次数+1
            result++
            j = next[j]
            i--
        }
    }
    return result
}
func GetNext(s string) []int {
    next := make([]int, len(s) +1 )
    next[0] = -1
    k := -1
    j := 0
 
    for j < len(s)-1 {
        if k == -1 || s[k] == s[j] {
            k++
            j++
            next[j+1] = k
        }else{
            k = -1 //回归首节点
        }
    }
 
    return next
}

Go 解法, 执行用时: 3ms, 内存消耗: 1348KB, 提交时间: 2021-04-23

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
*/
func kmp(S string, T string) int {
    next := getNext(S)
    return getCount(next, S, T)
}
func getNext(needle string) []int {
    next := make([]int, len(needle))
    for i, j := 1, 0; i < len(needle); i++ {
        for j > 0 && needle[i] != needle[j] {
            j = next[j - 1]
        }
        if needle[i] == needle[j] {
            j++
        }
        next[i] = j
    }
    return next
}
func getCount(next []int, needle string, haystack string) int {
    count := 0
    for i, j := 0, 0; i < len(haystack); i++ {
        for j > 0 && haystack[i] != needle[j] {
            j = next[j - 1]
        }
        if haystack[i] == needle[j] {
            j++
        }
        if j == len(needle) {
            count++
            j = next[j - 1]
        }
    }
    return count
}

Go 解法, 执行用时: 3ms, 内存消耗: 1404KB, 提交时间: 2021-05-02

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
*/
func kmp(S string, T string) int {
	m := len(S)
	n := len(T)
	next := getNext(S)
	ans := 0
	for i, j := 0, 0; i < n; {
		// when j = -1, we should move i to next, j(is -1) set to 0.
		if j == -1 || S[j] == T[i] {
			i++
			j++
		} else {
			j = next[j]
		}
		// find matching, if will want to find more, we must continue.
		if j == m {
			j = next[j]
			ans++
		}
	}
	return ans
}

// kmp next
// next[j]=k, j is the position of mismatching on pattern, k is the new position should jump to.
func getNext(pattern string) []int {
	m := len(pattern)
	next := make([]int, m + 1)
	next[0] = -1
	k, j := -1, 0
	for j < m {
		if k == -1 || pattern[k] == pattern[j] {
			j++
			k++
			next[j] = k
		} else {
			k = next[k]
		}
	}
	return next
}

C++ 解法, 执行用时: 4ms, 内存消耗: 784KB, 提交时间: 2021-07-25

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int kmp(string S, string T) {
        // write code here
        int count = 0;
        int next[S.size()];//结果和next数组，next[x]的意义是长度为x的前子串最长相同前后缀长度
        int j = 0;//j:前缀起始位置, i: 后缀起始位置
        next[0] = 0;
        for(int i = 1; i < S.size(); i++){
            while(j > 0 && S[i] != S[j]){// j要保证大于0，因为下面有取j-1作为数组下标的操作
                j = next[j-1];//前缀和后缀不相等,找上一次最长前后缀对应的位置回退
            }
            if(S[i] == S[j]) j++;//前缀后缀相等,i,j均后移一位
            next[i] = j;//最长前后缀长度
        }
        j = 0;
        for(int i = 0; i < T.size(); i++){
            while(j > 0 && T[i] != S[j]){
                j = next[j-1];//如果不匹配,回到前缀表上一个位置对应的位置重新匹配
            }
            if(T[i] == S[j]){
                j++;
            }
            if(j == S.size()){
                count++;
                j = next[j-1];
            }
        }
        return count;
    }
};

详情