给你一个文本串 T ,一个非空模板串 S ,问 S 在 T 中出现了多少次
数据范围:
要求:空间复杂度 ,时间复杂度
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; }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 计算模板串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; }
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) { 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; } }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 计算模板串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 };
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
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; } };
// 超时算法 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) { // 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; } } }
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; }
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; } }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 计算模板串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 };
# 计算模板串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
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; } };