给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次
数据范围：%20%5Cle%20500000%2C%0A%0A1%20%5Cle%20len(T)%20%5Cle%201000000%0A)
要求：空间复杂度 ))
，时间复杂度 %2Blen(T)))
[编程题]kmp算法
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)
这个算法是别人研究了3年才发布的，没有那么简单，主要核心思想是构建部分前缀后缀数组， 比如 T = ABCABD， 如果在 S = ABCABFGH 时，匹配到第六个元素的时候，T 和 S 不相等，此时应该避免从第二个开始匹配，而是从下一个 AB 即第四个开始匹配，如何确认从哪个开始匹配就需要构建前缀后缀数组，对于 T 的数组 pi = [0,0,0,1,2,0] 可知，对应的第二个 B 的值为2， 即我们就可以从当前的匹配到的下标 i - 2 开始继续向右匹配，因为它也是 AB 开头的，这样就避免了中间的重复的过程，有人可能还会疑惑，如果 T = ABABABC ， S = ABABABD 呢，当匹配到D 的时候也不匹配，此时应该从中间的 AB 开始继续重新匹配，而不是最后一个 AB， 实际上事实也是如此，因为 T = ABABABC 时，它的最大前缀后缀数组就为 pi = [0,0,1,2,3,4,0], 此时重新匹配的位置就为 i - 4 , 即从中间的 AB 开始匹配 ，因此优先求出匹配串的最长前缀后缀长度数组非常重要，如下是如何求解：
如 ABABCDA：
前缀：[A] [AB] [ABA] [ABAB] [ABABC] [ABABCD] [ABABCDA]
后缀: [A] [DA] [CDA] [BCDA] [ABCDA] [BABCDA] [ABABCDA]
pi = [0, 0, 1, 2, 0, 0, 1]
发表于 2024-05-24 21:39:54
回复(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)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算模板串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) {
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();
}
发表于 2024-11-07 13:47:41
回复(0)
class Solution: def kmp(self, S: str, T: str) -> int: # write code here # 运行超时 len_s = len(S) len_t = len(T) res = 0 for i in range(len_t - len_s + 1): if S == T[i : i + len_s]: res +=1 return res
超时了，汗
发表于 2024-10-29 15:57:30
回复(0)
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;
}
}
发表于 2024-10-18 20:10:29
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算模板串S在文本串T中出现了多少次
* @param S string字符串 模板串
* @param T string字符串 文本串
* @return int整型
*/
#include <string.h>
int ne[100000];
void getNext(char* a, int next[])
{
int j = 0;
next[0] = 0;
for(int i = 1; i < strlen(a); i++)
{
while(j > 0 && a[i] != a[j])
{
j = next[j - 1]; //回到前一个，相当于自身做了一次kmp
}
if(a[i] == a[j])
{
j++;
}
next[i] = j;
}
}
int kmp(char* S, char* T ) {
// write code here
int i = 0 , j = 0, count = 0;
int slen = strlen(S);
int tlen = strlen(T);
getNext(S, ne);
for(i = 0; i < tlen; i++)
{
if(j == 0 && tlen - i < slen)
break;
while(j > 0 && T[i] != S[j])
{
j = ne[j - 1];
}
if(T[i] == S[j])
{
j++;
}
if(j == slen)
{
count++;
j = ne[j - 1];
}
}
return count;
}
还是跑不完，只能跑5组测试用例，数一大还是超时，还望老哥们赐教
发表于 2024-09-25 21:06:44
回复(0)
// 参考B站左程云大佬的KMP算法讲解
public int kmp (String S, String T) {
// write code here
char []s1 = S.toCharArray();
char []s2 = T.toCharArray();
int n = s1.length, m = s2.length;
if (n > m || m == 0) return 0;
int cnt = 0;
int x = 0, y = 0;
int index = 0;
int []next = nextArray(s1, n);
while (x < m) {
if (y == n-1&&s1[y] == s2[x]) {
cnt++;
y=next[y];
}
if (s1[y] == s2[x]) {
x++;
y++;
} else if (y == 0) {
x++;
} else {
y = next[y];
}
}
return cnt;
}
/**
得到next数组
*/
public int[] nextArray(char []s, int m) {
if (m == 1) {
return new int[] {-1};
}
int []next = new int[m];
next[0] = -1;
next[1] = 0;
int i = 2, cn = 0;
while (i < m) {
if (s[i - 1] == s[cn]) {
next[i++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
}
发表于 2024-05-25 23:13:54
回复(0)
using System;
using System.Collections.Generic;
class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算模板串S在文本串T中出现了多少次
* @param S string字符串 模板串
* @param T string字符串 文本串
* @return int整型
*/
public int kmp (string S, string T) {
// write code here
if (string.IsNullOrWhiteSpace(S) || string.IsNullOrWhiteSpace(T))
return 0;
if (S.Length > T.Length)
return 0;
if (S.Length == T.Length)
return S.Equals(T) ? 1 : 0;
int nCountTimes = 0;
for (int nIndex = 0; nIndex <= T.Length - S.Length; nIndex++) {
int nIndexSec = 0;
for (; nIndexSec < S.Length &&
S[nIndexSec].Equals(T[nIndex + nIndexSec]); nIndexSec++) { }
if (nIndexSec != S.Length)
continue;
nCountTimes++;
}
return nCountTimes;
}
}
编辑于 2024-03-29 22:38:16
回复(0)
// 超时算法
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)
问题信息
难度：
65条回答
554收藏
8568浏览
通过挑战的用户
查看代码-
2023-02-04 20:01:37 -
2022-10-04 13:06:13 -
2022-09-20 21:53:21
-
2022-09-17 07:46:02 -
2022-09-16 15:09:07
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
