首页 > 试题广场 >

kmp算法

[编程题]kmp算法
  • 热度指数:30723 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给你一个文本串 T ,一个非空模板串 S ,问 S 在 T 中出现了多少次

数据范围:
要求:空间复杂度 ,时间复杂度
示例1

输入

"ababab","abababab"

输出

2
示例2

输入

"abab","abacabab"

输出

1
function kmp(S, T) {
    if (!S || !T || T.length < S.length) return 0;
    const next = getNext(S);
    return getCount(next, S, T);
}
function getNext(needle) {
    const next = Array(needle.length).fill(0);
    for (let i = 1, j = 0; i < needle.length; ++i) {
        while (j > 0 && needle[i] !== needle[j]) j = next[j - 1];
        if (needle[i] === needle[j]) j++;
        next[i] = j;
    }
    return next;
}
function getCount(next, needle, haystack) {
    let count = 0;
    for (let i = 0, j = 0; i < haystack.length; i++) {
        while (j > 0 && haystack[i] !== needle[j]) j = next[j - 1];
        if (haystack[i] === needle[j]) ++j;
        if (j === needle.length) {
            count++;
            j = next[j - 1];
        }
    }
    return count;
}

发表于 2021-04-22 15:34:03 回复(1)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
 */
int kmp(char* S, char* T ) 
{
    // write code here
    int a,i,j,n=0;
    a=strlen(S);
    for(i=0;T[i]!='\0';i++)
    {
        for(j=0;j<a;j++)
        {
            if(S[j]!=T[i+j])
            {
                break;
            }
        }
        if(j>=a)
        {
            n++;
        }
    }
    return n;
}
发表于 2021-02-02 23:50:52 回复(0)
public class Solution {
    public int kmp (String S, String T) {
        int res = 0;
        int[] next = new int[S.length()];
        getNext(next, S);
        int j = 0;
        int i = 0;
        while (i < T.length()) {
            // 退到头或相等,i指针往后
            if (j == 0 || T.charAt(i) == S.charAt(j)){
                i++;
                j++;
            }
            else { // j回退,防止溢出
                if (j == 0) j = 0;
                else j = next[j - 1];
            }
            if (j == S.length()){ // 找到一个子串,j回退
                res++;
                j = next[j - 1];
            }
        }
        return res;
    }
    void getNext(int next[], String S){
        int j = 0;
        next[0] = 0; // 初始化
        for (int i = 1; i < S.length(); i++) {
            // 前缀不相同时;注意此处回退循环,退到相等
            while (j > 0 && S.charAt(i) != S.charAt(j)) 
                j = next[j - 1];
            // 前缀相同时,更新前缀指针和next数组
            if (S.charAt(i) == S.charAt(j)) {
                j++;
                next[i] = j;
            }
        }
    }
}
人家三个学者提出来的算法,没提前学过或专门学过,基本没人能直接写出来。完整学过理解之后才能模仿实现,这种题也能算中等题?。。
发表于 2021-11-23 22:36:07 回复(1)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        return find(T,S);
    }
    int find(String source,String pattern){
        int n1=source.length();
        int n2=pattern.length();
        char []par=pattern.toCharArray();
        char[]sour=source.toCharArray();
        int[]next=new int[n2];
        int k=-1;
        next[0]=-1;
        //构建next数组,其中第next[i]表示par模式串数组中最长公共前缀后缀的前缀结束的下标
        // par="aabaac" next[0]=-1 next[1]=1 next[2]=-1 next[3]=1 next[4]=1 next[5]=-1
        for(int i=1;i<n2;i++){
            while(k!=-1&&par[k+1]!=par[i])k=next[k];
            if(par[k+1]==par[i])k++;
            next[i]=k;
        }
        k=-1;
        int ans=0;
        for(int j=0;j<n1;j++){
            //如果匹配 j++,k++
            if(sour[j]==par[k+1])k++;
            else{
                //不匹配则在模式串中,继续向前搜索
                //比如pattern aabaac
                //待查找的串 aaeefaagef
                //     aeefaagef              aeefaagef
                //         aabaac                 aabaac
                //           |该位置不匹配 next[1]=0|
                while(k!=-1&&par[k+1]!=sour[j])k=next[k];
            }
            if(k==n2-1){
                int pre=j-pattern.length()+2;
                ans++;
                j=pre;
                k=-1;
            }
        }

        return ans;
    }
}

发表于 2021-07-03 10:04:07 回复(3)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
 */
function kmp( S ,  T ) {
    var index = T.indexOf(S);
    var count = 0;
    while(index > -1) {
        count++;
        index = T.indexOf(S, index + 1);
    }
    return count;
    
}
module.exports = {
    kmp : kmp
};

发表于 2023-10-18 21:06:59 回复(0)
python kmp算法进行字符串匹配
class Solution:
    def kmp(self , S , T ):
        # kmp算法参考leetcode 28
        # 不同于kmp,这里还需统计匹配的次数
        m = len(T)
        n = len(S)
        # 创建next数组
        nex = [0] * n
        count = 0
        j = 0
        # 计算next数组
        for i in range(1, n):
            while j > 0 and S[j] != S[i]:
                j = nex[j-1]
            if S[j] == S[i]:
                j += 1
            nex[i] = j
        # kmp字符串匹配
        j = 0
        for i in range(m):
            while j > 0 and S[j] != T[i]:
                j = nex[j-1]
            if S[j] == T[i]:
                j += 1
            # 判断是否完成完整匹配
            if j == n:
                count += 1
                j = nex[j-1]
        # 返回出现个数
        return count
发表于 2021-08-24 15:38:42 回复(0)
class Solution {
public:
    int kmp(string S, string T) {
        // write code here
        int ans=0;//记录出现次数
        //先求next数组-前缀表        
        int next[S.size()];
        next[0]=0;
        int j=0;
        for(int i=1;i<S.size();i++){
            //前后缀不相同时
            while(j>0&&S[i]!=S[j]){
                j=next[j-1];//回退
            }
            //前后缀相同时
            if(S[i]==S[j]){
                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()){//j==S.size():说明已经遍历完找到一个了
                ans++;
                j=next[j-1];
            }
        }
        return ans;
    }
};

编辑于 2021-07-15 09:20:32 回复(0)
    public int kmp (String S, String T) {
      int time=0;
      int longLen=T.length(),shortLen=S.length();
      for(int i=0;i<=longLen-shortLen;i++){
          if(S.equals(T.substring(i,shortLen+i)))
              time++;
      }
        return time;
    }

编辑于 2021-03-14 10:40:25 回复(3)
// 超时算法
public int kmp (String S, String T) {
    // write code here
    int ls=S.length() ,lt=T.length() ,res=0;
    for(int i=0;i+ls<=lt;i++){
        if(S.equals(T.substring(i,i+ls))){
            res++;
        }
    }
    return res;
}

发表于 2024-03-24 14:13:43 回复(0)
还蛮难,本质也是dp思想,背吧
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        // write code here
        /** 暴力解
            int count = 0;
            for(int i = 0; i <= T.length() - S.length(); i++) {
                int len = 0;
                for(; len < S.length(); len++) {
                    if(S.charAt(len) != T.charAt(i + len)) break; 
                }
                if(len == S.length()) count++;
            }
            return count;
         */
        int[] next = new int[S.length()];
        getNext(next, S);
        int res = 0;
        int startS = 0;
        for(int i = 0; i < T.length(); i++) {
            while((startS > 0) && (S.charAt(startS) != T.charAt(i))) {
                startS = next[startS - 1];
            }
            // 两种情况,0都不匹配,那就下一个i从头开始
            if(S.charAt(startS) == T.charAt(i)) startS++;
            // 匹配成功,重置
            if(startS == S.length()) {
                res++;
                startS = next[startS - 1];
            }
        }
        return res;
        
    }

    // 前缀数组初始化
    private void getNext(int[] next, String s) {
       // next[i]的含义就是(0 - i)串的最大前缀后缀和
       // 实际上也是dp递归思路求解
       int endPrefix = 0;
       for(int i = 1; i < next.length; i++) {
            while((endPrefix > 0) && (s.charAt(endPrefix) != s.charAt(i))) {
                endPrefix = next[endPrefix - 1];
            }
            int maxLen = endPrefix;
            if(s.charAt(endPrefix) == s.charAt(i)) {
                maxLen = maxLen + 1;
                endPrefix++;
            }  
            next[i] = maxLen;
       }
    }
}


发表于 2024-01-13 16:53:39 回复(0)
class Solution:
    def kmp(self , S: str, T: str) -> int:
        # write code here
        def pre_process(S):
            '''
            输出前缀表
            '''
            next_string = [0]*len(S)
            j = 0
            for  i in range(1,len(S)):
                while j >0 and S[j] != S[i]:
                    j = next_string[j-1]
                if S[i] == S[j]:
                    j+=1
                next_string[i] = j
            return next_string

        next_string = pre_process(S)
        j = 0  #指向S的当前字符
        count = 0 #记录S在T中出现的次数
        for i  in range(len(T)):
            while j >0 and T[i] !=S[j]:
                j = next_string[j-1]
            if T[i] == S[j]:
                j+=1
            if j == len(S):  #如果把S遍历完全,则视为出现一次
                count +=1
                j = next_string[j-1]
        return count
编辑于 2023-12-21 00:21:56 回复(0)
题目都没读懂
发表于 2023-09-09 15:27:09 回复(0)
def count_num():
    str_1,string = input().split(",")
    str_1=str_1[1:len(str_1)-1]
    string =string[1:len(string)-1]
    length = len(str_1)
    count = 0
    for i in range(len(string)):
        if str_1 == string[i:length+i]:
            count += 1
        else:
            continue
    return count
while True:
    try:
        print(count_num())
    except:
        break
发表于 2023-05-28 01:46:18 回复(0)
int kmp(string S, string T) 
    {
        int res=0;
        vector<int>ne(T.size());
        ne[1]=0;
        for(int i=1,j=0;i<S.size();i++)
        {
            while(j && S[i]!=S[j]) j=ne[j-1];
            if(S[i]==S[j]) j++;
            ne[i]=j;
        }
       
        for(int i=0,j=0;i<=T.size();i++)
        {
            while(j && T[i]!=S[j]) j=ne[j-1];
            if(T[i]==S[j]) j++;
            if(j==S.size())
            {
                res++;
                j=ne[j-1];
            }
        }
        // write code here
        return res;
    }

发表于 2023-05-11 18:13:04 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        if (S.length() == 0 || S.length() > T.length()) return 0;
        int[] next = getNext(S);
        int j = 0, count = 0;
        for (int i = 0; i < T.length(); i++) {
            while (j > 0 && S.charAt(j) != T.charAt(i)){
                j = next[j - 1];
            }
            if (S.charAt(j) == T.charAt(i)){
                j++;
            }
            if (j == next.length){
                count++;
                //匹配成功后,计数,按照当前未匹配成功,回退next[]
                j = next[j - 1];
            }
        }
        return count;
    }
    public int[] getNext(String s){
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)){
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

发表于 2023-05-09 20:56:33 回复(0)
   //检测是否有某个字串 S 子串
    //得出字串的前缀和后缀最大长度
    //遍历T 和S  不相等  回到前缀表上一个位置进行匹配
   let next = [0]
   let j = 0
   for(let i = 1;i<S.length;i++){
    if(j>0 && S[j]!=S[i]){
        j = next[j-1]  //不相等,回到前缀表上一个位置对应的位置重新匹配
    }
    if(S[i]==S[j]){
        j++;
    }
    next.push(j)
   }
   let count = 0;
   let k = 0
   for(let i=0;i<T.length;i++){
    if(k>0 && T[i]!=S[k]){
        k = next[k-1]
    }
     if(T[i]==S[k]){
        k++;
     }
     if(k==S.length){
        count++;
        k = next[k-1]
     }
   }
   return count;
发表于 2023-04-26 15:36:12 回复(0)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
 */
function kmp( S ,  T ) {
    // write code here
    // 模板中不重复的字母
    let m = Array.from(new Set(S.split(""))) 
    let n = S.length+1
    // 初始化状态转移矩阵
    let dp = new Array(n).fill(0).map(v=>new Array(m.length).fill(0))
    // 影子状态
    let X = 0
    dp[0][0] = 1
    // 构建状态转移矩阵
    for(let j=1;j<n;j++){
        let c = S.charAt(j)
        for(let i=0;i<m.length;i++){
            dp[j][i] = dp[X][i]
            // 则c为空,复制影子状态,但不更新
            if(m[i]==c){
                dp[j][i] = j+1
            }
        }
        X = dp[X][m.indexOf(c)]
    }
    let stage = 0
    let num = 0
    for(let k=0;k<T.length;k++){
        let index = m.indexOf(T.charAt(k))
        stage = dp[stage][index]
        if(stage==S.length){
            num++
        }
    }
    return num
}
module.exports = {
    kmp : kmp
};

发表于 2023-03-28 12:58:32 回复(0)
# 计算模板串S在文本串T中出现了多少次
# @param S string字符串 模板串, 子串
# @param T string字符串 文本串, 主串
# @return int整型
class Solution:
    def kmp(self , S: str, T: str) -> int:
        # write code here
        '构造next数组'
        '''伪代码
            if S[i]==S[j]:
                i++,j++,next[i]=j
            elif S[i]!=S[j]
                if j==0, next[i]=0=j,i++
                elif j!=0, j = next[j-1]
        '''
        j = 0 # 被比较的下标,初始化为0
        next = [0]*len(S)
        for i in range(1, len(S)): # i循环下标,初始化为1
            if S[i] == S[j]:
                j += 1
                next[i] = j
            else: 
                if j != 0:
                    while j != 0 and S[i] != S[j]:
                        j = next[j-1]
                else: 
                    next[i] = j
        '子串S去匹配主串T'
        '''伪代码
        如果两个串的对应字符相等,索引都+1
        如果不相等,子串的j=0时,主串的索引i+1;j不等于0时,j = next[j-1]
        如果子串循环完成,次数+1,同时更新j,j = next[j-1]
        '''
        i, j = 0, 0
        res = 0 # 次数
        while i < len(T):
            if T[i] == S[j]:
                i+=1
                j+=1
            else:
                if j > 0:
                    j = next[j-1]
                else: # j == 0, 头一个就匹配失败
                    i += 1
            if j == len(S):
                res += 1 # 出现次数+1
                j = next[j-1]
        return res

发表于 2023-03-23 14:56:57 回复(0)
from re import S

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 计算模板串S在文本串T中出现了多少次
# @param S string字符串 模板串
# @param T string字符串 文本串
# @return int整型
#
# class Solution:
#    def kmp(self , S: str, T: str) -> int:
#       # write code here

import time
# 接收输入
S = input()

t1=time.time()
# 将S模板存入列表1
L1 = S.split(",")[0]

L1 = L1[1 : len(L1) - 1]
# 对输入的""进行处理
# print(len(L1))

# 将文本串存入列表2
L2 = S.split(",")[1]
L2 = L2[1 : len(L2) - 1]
#
L3 = []

# 定义列表L3接收可能符合情况的列表的索引
for k, v in enumerate(L2):
    # print(k,v)
    if L1[0] == v:
        L3.append(k)
# print(L1[0][0])
#print(L3)
def func(L1,L2,L3):
    count = 0
    for x in L3:
        i = 0
        while i < len(L1):
            if x < len(L2):
                if L1[i] == L2[x]:
                    i += 1
                    x += 1
                elif L1[i] != L2[x]:
                    count -= 1
                    break
            else:
                return count
        count += 1
    return count
print(func(L1,L2,L3))

发表于 2023-02-13 20:56:28 回复(0)
Kmp

class Solution {
  public:
    int kmp(string S, string T) {
        int ans = 0;
        int next[S.size()];
        next[0] = -1;
        int i = 0, j = -1;

        for (i = 0; i < S.size() - 1; ) {
            if (j == -1 || S[i] == S[j]) {
                i++;
                j++;
                next[i] = j;
            } else
                j = next[j];
        }

        i = 0, j = 0;
        while (i < T.size() && j < S.size()) {

            if (T[i] == S[j]) {
                ++j;
                ++i;
            } else {
                j = next[j];

            }
            //解除j回退到-1时, -1大于size的bug
            if (j == -1) {
                ++j;
                ++i;
            }
            /*匹配完了,上一个字符匹配成功,
            相当于匹配了上个字符的next[],所以运行到next[j -1]后,+1*/
            if (j == S.size()) {

                ans++;
                j = next[j - 1] + 1;
            }
        }

        return ans;
    }
};



发表于 2023-01-18 23:21:29 回复(1)