首页 > 试题广场 >

kmp算法

[编程题]kmp算法

热度指数：31116 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次

数据范围： $1 \le len(S) \le 500000, 1 \le len(T) \le 1000000$

要求：空间复杂度 $O(len(S))$ ，时间复杂度 $O(len(S)+len(T))$

示例1

输入

"ababab","abababab"

输出

示例2

输入

"abab","abacabab"

输出

算法知识视频讲解

Java

牛客839384289号

// 超时算法
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)

Java

疯狂的小企鹅

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)

Java

牛客2077166号

这题不是中等难度

发表于 2022-08-27 18:43:36 回复(0)

Java

keduoli

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 ans = 0;
        
        char[] sBuf = S.toCharArray();
        char[] tBuf = T.toCharArray();
        
        int[] next = new int[S.length()];
        
        getNext(sBuf, next);
        
        int i = 0, j = 0;
        
        while (i < tBuf.length) {
            if (tBuf[i] == sBuf[j]) {
                i++;
                j++;
            } else if (j > 0) {
                j = next[j - 1];
            } else {
                i++;
            }
            
            if (j == sBuf.length) {
                ans++;
                j = next[j - 1];
            }
        }
        
        return ans;
        
    }
    
    void getNext(char[] buf, int[] next) {
        
        int j = 0, i = 1;
        next[0] = 0;
        
//         char[] buf = S.toCharArray();
        while (i < buf.length) {
            if (buf[i] == buf[j]) {
                next[i++] = ++j;
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    next[i++] = 0;
                }
            }
        }
        
    }
    
    
}

发表于 2022-03-20 23:55:31 回复(0)

Java

牛客834967964号

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)

Java

MOMO-酱

//超时了，咋优化

public int kmp (String T, String S) {
// write code here
int a=0;
int b=0;
while(a!=-1){
if(S.indexOf(T,a)==a){
++a;
++b;
}
a=S.indexOf(T,a);
}
return b;
}

发表于 2021-10-18 16:36:12 回复(0)

Java

TylerChen

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        char[] t = T.toCharArray(), p = S.toCharArray();
        int i1 = 0, i2 = 0, res = 0;
        int[] next = next(p);
        while(i1 < t.length && i2 < p.length){
            if(t[i1] == p[i2]){
                i1 ++;
                i2 ++;
            }else if(next[i2] == -1){
                i1 ++;
            }else {
                i2 = next[i2];
            }
            if(i2 == p.length){
                res ++;
                i2 = next[i2-1];
                i1 --;
            }
        }
        if(i2 == p.length){
            
        }
        return res;
        
    }
    
    
    int[] next(char[] p){
        if(p.length == 1){
            return new int[]{-1};
        }
        int[] next = new int[p.length];
        next[0] = -1;
        next[1] = 0;
        //cn 表示next[i-1]
        int i = 2, cn = 0;
        while(i < p.length){
            if(p[i - 1] == p[cn] ){
                next[i ++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else {
                next[i++] = 0;
            }
        }
        return next;
        
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}

发表于 2021-07-31 16:08:56 回复(0)

Java

localking

截取字符串匹配

public class Solution {
    public int kmp (String S, String T) {
        // write code here
         int result=0;
         for(int i=0;i<T.length();i++) { 
         int ff=i+S.length();
         if(ff<=T.length()) {
         String fsString= T.substring(i, ff);
         if(S.equals(fsString)) {
            result++; 
         }
        }
    }
         return result;
    }
}

发表于 2021-07-16 20:51:44 回复(3)

Java

牛客2595270号

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算模板串S在文本串T中出现了多少次
* @param S string字符串模板串
* @param T string字符串文本串
* @return int整型
*/
public int kmp (String S, String T) {
int count = 0;
// 滑动的次数
for(int i=0;i<=T.length() - S.length();i++) {
String windowStr = T.substring(i, i + S.length());
if(S.equals(windowStr)) {
count++;
}
}
return count;
}

发表于 2021-06-14 00:04:13 回复(0)

Java

惠灵顿靖

public class Solution {
    public int kmp (String S, String T) {
        int time=0;
        int shortlen=S.length(),longlen=T.length();
        for(int i=0;i<=longlen-shortlen;i++){
            if(S.equals(T.substring(i,shortlen+i)))time++;
        }
        return time;
    }}

发表于 2021-04-12 15:22:02 回复(3)

Java

小唐哥

好无奈啊，求优化；

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算模板串S在文本串T中出现了多少次
* @param S string字符串模板串
* @param T string字符串文本串
* @return int整型
*/
public int kmp1 (String S, String T) {
int n=0;
for(int i=0; i< T.length();i++){
if(i> (T.length() - S.length())) break;
int t = T.indexOf(S,i);
if(t != -1) n++;
}
return n;
}

public int kmp (String S, String T) {
int n=0;
char[] s0= S.toCharArray();
char[] t0= T.toCharArray();
for(int i=0; i< t0.length;i++){
if(i > (T.length() - S.length())) break;
if(t0[i] == s0[0]){
int j=1,k=i+1;
do{
if(t0[k]== s0[j]){
j++;
k++;
}else{
break;
}
}while(j < s0.length && k < t0.length);
if(s0.length ==j) n++;
}
}
return n;
}
}

编辑于 2021-04-05 18:42:25 回复(0)

Java

花落梦里

    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)