首页 > 其他分享 >KMP

KMP

时间:2024-05-06 15:33:06浏览次数:17  
标签:int KMP char 点击 nex 120000

先放着

点击查看代码
	nxt[0]=-1;
	int j=0;
	for(int i=2;i<=len2;i++)
	{
		while(j&&s2[j+1]!=s2[i]) j=nxt[j];
		if(s2[j+1]==s2[i]) j=j+1;
		nxt[i]=j;
	}//自己匹配
	
	j=0;
	for(int i=1;i<=len1;i++)
	{
		stk[++top]=i;
		while(j&&s2[j+1]!=s1[i]) j=nxt[j];
		if(s2[j+1]==s1[i]) j=j+1;
	}//与别人匹配
点击查看代码
#include<bits/stdc++.h>
using namespace std;
char s1[120000];
int nex[120000];
int n,m;
char s2[120000];
int len1;
void nx(char str[]){
	int j=0;
	nex[0]=-1;
	for(int i=2;i<=len1;i++){
		while(j&&str[j+1]!=str[i]) j=nex[j];
		if(str[j+1]==str[i]) j++;
		nex[i]=j;
	}
}
int kmp(char str[]){
	int len=strlen(str+1),j=0;
	for(int i=1;i<=len;i++){
		while(j&&s1[j+1]!=str[i]) j=nex[j];
		if(s1[j+1]==str[i]) j++;
		if(j==len1) return 1;
	}
	return 0;
}
int main(){
	scanf("%s",s1+1);
	len1=strlen(s1+1);
	nx(s1);
	cin>>n;
	for(int i=1;i<=n;i++){
		memset(s2,0,sizeof(s2));
		scanf("%s",s2+1);
		if(kmp(s2)) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

标签:int,KMP,char,点击,nex,120000
From: https://www.cnblogs.com/PeppaEvenPigShiGeNiuBDePig/p/18173672

相关文章

  • 寻根KMP算法
    本人被\(KMP\)已经折磨许久。五战KMP。方知之前理解确实浅。故写此篇。这是之前那篇,实在是太浅,不过对代码做了注释。https://www.acwing.com/solution/content/131255/本篇重点说明\(KMP\)的原理,而非过程。过程相信其他博客已经写的十分完善了。\(KMP\)算法(\(Knuth-Morris-......
  • 字符串基础(hash,KMP,AC自动机,trie)
    trie树trie树,又叫字典树,就是把字符串的每个字母看做树上的一个节点,若干个字符串组成了一棵trie树。最一般的trie树好像只能搜索字符串,重点是01trie和可持久化trie树和用trie树来建ac自动机(详见AC自动机)。这里着重介绍一下01trie01trie,就是节点代表了数上的二进制位上的数。......
  • $KMP$学习记
    《不浪漫罪名》没有花这刹那被破坏吗无野火都会温暖吗无烟花一起庆祝好吗若爱恋仿似戏剧那样假如布景一切都美化连相拥都参照主角吗你说我未能定时令你每天欢笑一次我没说出一句美丽台词是你心中一种缺陷定义流进了眼角里的刺为何不浪漫亦是罪名为何不轰烈是件坏......
  • P3375 【模板】KMP
    https://www.luogu.com.cn/problem/P3375#include<bits/stdc++.h>usingnamespacestd;constintN=1e7+5;vector<int>get_pi(strings){ intn=s.length(); vector<int>pi(n); for(inti=1;i<n;++i){ intj=pi[i-1]; while(j&&s[i......
  • 字符串基础:Hash,KMP,trie
    Hash把一个字符串映射成一个整数,可以方便的比较两个字符串是否相等,计算\(Hash\)值:\[\displaystyle\sum_{i=0}^{len-1}(s[i]\timesB^{len-1-i})(mod\;M)\]这里的\(B\)是任取的一个大小合适的数,\(M\)就是为了把算出来的值映射到\([0,M-1]\)的范围内,既然是\(mod\),......
  • 数据结构——入门到飞升——kmp算法
    给定一个字符串text和一个模式串pattern,求pattern在text中的出现次数。text和pattern中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern可重叠。输入格式:输入共两行,分别是字符串text和模式串pattern。输出格式:输出一个整数,表示pattern在text......
  • KMP
    KMP算法一个人能能走的多远不在于他在顺境时能走的多快,而在于他在逆境时多久能找到曾经的自己。————KMP​板子介绍两个部分分别实现了next数组的构造和匹配的过程。本文均是从下标1开始的。(写题的时候就这么做即可,中间过程无虚任何改动)最后打印的时候(看样例加和减即可)......
  • KMP算法
    KMP算法KMP算法的核心思想是利用模式串自身的特性,在匹配过程中尽量避免回溯,以提高匹配的效率。它通过构建一个部分匹配表(也称为next数组),来指导匹配过程中模式串的移动位置,从而减少不必要的字符比较。KMP算法的基本步骤1.构建部分匹配表(next):遍历模式串,对于每个位置i,找出以......
  • KMP算法 Java实现
    Problem:28.找出字符串中第一个匹配项的下标目录解题方法思路构建next数组回溯查找复杂度Code解题方法构建next串回溯查找next串,最后下标思路通过最大前缀后缀能找到下一次未查找到后要回溯的位置构建next数组无论如何第一个数的下一次回溯位置肯定是0,因此next[......
  • KMP 相关
    KMPT1CensoringS给定一个文本串\(S\)和一个模式串\(T\),反复从\(S\)中删去最左边的完整出现的\(T\),然后把左右两部分接起来视作新的文本串\(S\),请问\(S\)的最终形式。\(1\leq|T|\leq|S|\leq10^6\)。T2OKR-PeriodsofWords我们认为\(Q\)是\(S\)的周期仅当......