kmp算法

    public int kmp (String S, String T) {
        final int sLength = S.length();
        final AtomicInteger count = new AtomicInteger();
        Queue<Character> sQueue = new LinkedList<>();
        Queue<Character> tQueue = new LinkedList<>();
        IntStream.range(0, sLength).forEach(index -> {
            sQueue.offer(S.charAt(index));
            tQueue.offer(T.charAt(index));
        });
        if (sQueue.hashCode() == tQueue.hashCode()) {
            count.getAndIncrement();
        }
        IntStream.range(0, T.length()-sLength).forEach(index -> {
            tQueue.poll();
            tQueue.offer(T.charAt(index + sLength));
            if (sQueue.hashCode() == tQueue.hashCode()) {
                count.getAndIncrement();
            }
        });
        return count.get();
    }

import java.util.*;

public class Solution {
    public int kmp(String S, String T) {
     
        int M = S.length();
        int N = T.length();

        // 创建lps[]数组，保存模式串的前缀函数
        int[] lps = LPS(S);

        // 初始化两个指针i和j，分别指向文本T和模式串S的当前位置
        int i = 0;
        int j = 0;
        // 初始化计数器count，用于记录模式串S在文本T中出现的次数
        int count = 0;

        // 遍历文本T，直到指针i到达文本的末尾
        while (i < N) {
            // 如果模式串S的当前字符与文本T的当前字符相同，则两个指针都向前移动
            if (S.charAt(j) == T.charAt(i)) {
                j++;
                i++;
            }
            // 如果模式串S已经完全匹配，则增加计数器，并根据lps数组将模式串的指针j回溯到合适的位置
            if (j == M) {
                count++;
                j = lps[j - 1];
            } else if (i < N && S.charAt(j) != T.charAt(i)) {
                // 如果当前字符不匹配，且模式串的指针j不为0，则根据lps数组将模式串的指针j回溯
                if (j != 0)
                    j = lps[j - 1];
                // 如果模式串的指针j为0，则只能将文本的指针i向前移动
                else
                    i = i + 1;
            }
        }
        return count;
    }

// 定义一个私有静态方法，用于计算模式串的前缀函数数组lps[]
    private static int[] LPS(String pattern) {
        // 初始化lps数组，长度与模式串相同
        int[] lps = new int[pattern.length()];
        // 初始化len为0，用于记录前缀的长度
        int len = 0;
        // 初始化i为1，因为lps[0]总是为0
        int i = 1;
        // lps[0]设置为0，因为模式串的第一个字符总是前缀
        lps[0] = 0;

        // 遍历模式串，计算每个位置的前缀长度
        while (i < pattern.length()) {
            // 如果当前字符与前缀的最后一个字符相同，则更新len和lps[i]
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                // 如果当前字符与前缀的最后一个字符不同，且len不为0，则根据lps数组回溯len
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    // 如果len为0，则更新lps[i]为0，并向前移动i
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}

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

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;
    }
}

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;
                }
            }
        }
        
    }
    
    
}

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;
            }
        }
    }
}

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;
        
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}

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;
    }}

    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;
    }