当前位置: 首页 > news >正文

蓝桥杯倒计时 41天 - KMP 算法

KMP算法

KMP算法是一种字符串匹配算法,用于匹配模式串P在文本串S中出现的所有位置。
例如S=“ababac,P=“aba”,那么出现的所有位置是13。
在初学KMP时,我们只需要记住和学会使用模板即可,对其原理只需简单理解,不要过度深究,避免把自己绕进去,可以课后自己慢慢去画图理解。
KMP算法将原本O(n2)的字符串匹配算法优化到了O(n).其精髓在于next数组,next数组表示此时模式串下标失配时应该移动到的位置,也表示最长的相同真前后缀的长度。
在这里插入图片描述
例如P=“ababac”,S=“abababac”。
当匹配到i=6,j=5,P[i+1]!=S[i]时,j不会移动到1重新开始匹配,而是移动到nex[j]=3继续匹配,
则接下来i=6,j=3,有P[j+1]=S[i],成功匹配,则i,j继续后移,直到i=8.j=6完成一次匹配,则P在S中第一次出现的位置为j-i+1=3。

计算next数组(next数组仅与模式串P有关)的方式就是用P自己去匹配自己,大家只需要掌握模板即可,暂时不要深究其原理。

char s[N],p[N];
int nex[M];
int n = strlen(s+1),m=strlen(p+1);//字符串下标从 1 开始
nex[0]=nex[1]=0;
for(int i=2,j=0;i<=m;++i){while(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;//从 while 出来后要么 j=0,要么 p[i]==p[j+1],如果匹配成果,则 j 后移nex[i]=j;//如果匹配失败就回到 j,因为此时 p[1~j]=p[i-j+1~j]或 j=0(回到最初的地方开始匹配)
}

通过 next 数组匹配

for(int i=1,j=0;i<=n;i++)
{while(j&&s[i]!=p[j+1])j=nex[j];if(s[i]==p[j+1])j++;if(j==m)//成功匹配一次
}

斤斤计较的小Z

在这里插入图片描述
思路:KMP 算法模板,不知道为啥结果不对

#include<bits/stdc++.h>
using namespace std;
const int N =20,M=20;
char s[N],p[M];
int nex[M];int main(){scanf("%s\n%s",p+1,s+1);int n=strlen(s+1),m=strlen(p+1);nex[0]=nex[1]=0;for(int i=2,j=0;i<=m;i++){while(j&&p[j+1]!=p[i])j=nex[j];if(p[j+1]==p[i])j++;nex[i]=j;}int res=0;for(int i=1,j=0;i<=n;i++){while(j&&p[j+1]!=s[i])j=nex[j];if(p[j+1]==s[i])j++;if(j==m)res++;}cout<<res<<'\n';return 0;
}

boarder

在这里插入图片描述
思路:利用 KMP 求整个串的最长真前后缀,len-nex[len]就是整个串的循环节,len 能整除循环节就是答案,不能就是 1。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char p[N];
int nex[N];
int main( ){scanf("%s",p+1);unsigned long m=strlen(p+1);nex[0]=nex[1]=0;for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;nex[i]=j;}int len=m-nex[m];if(m%len==0){cout<<m/len<<endl;}else{cout<<1<<endl;}return 0;
}

幸运字符串

在这里插入图片描述
在这里插入图片描述
思路:求 nex 数组,找最大值就是答案

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n;
char p[N];
int nex[N];
int main( ){cin>>n;scanf("%s",p+1);unsigned long m=strlen(p+1);for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;nex[i]=j;}int ans=0;for(int i=1;i<=m;i++)ans=max(ans,nex[i]);cout<<ans<<endl;return 0;
}

你也喜欢幸运字符串吗?

在这里插入图片描述
思路:动态规划+KMP,不会。
在这里插入图片描述

#include <bits/stdc++.h>
#define ll long long
#define PI 3.1415926
using namespace std;
typedef pair<int, int> vt;
typedef pair<vt, vt> PII;
const int N = 1e6 + 10;
const int M = 2 * N;
const int mod = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;int ne[N];
string s;
int n;void solve()
{cin >> n;cin >> s;memset(ne, 0, sizeof ne);s = " " + s;for (int i = 2, j = 0; i <= n; i++){while (j && s[i] != s[j + 1])j = ne[j];if (s[i] == s[j + 1])j++;ne[i] = j;}vector<ll> f(n + 5);for (int i = 1; i <= n; i++)f[i] = 1;for (int i = n; i >= 1; i--)f[ne[i]] += f[i];ll ans = 0;// for(int i=1;i<=n;i++)cout<<f[i]<<endl;for (int i = 1; i <= n; i++){if (ne[i] != 0)ans += f[ne[i]];}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);/*多组案例初始化*/// int t;cin>>t;while(t--)solve();
}
http://www.lryc.cn/news/311573.html

相关文章:

  • 《汇编语言》- 读书笔记 - 第13章-int 指令
  • 深入了解 Golang 条件语句:if、else、else if 和嵌套 if 的实用示例
  • 大数据和机器学习在气象预报中的应用-张平文院士
  • C#高级:Winform桌面开发中DataGridView的详解
  • java八股文复习-----2024/03/05----基础---反射,动态代理。序列化
  • 【人工智能】Anthropic发布强大的Claude3对齐GPT-4,大模型杂谈个人感想
  • 基于openKylin与RISC-V的MindSpore AI项目实践
  • 【牛客】VL64 时钟切换
  • Java设计模式——桥连模式
  • 数据结构与算法:堆排序和TOP-K问题
  • 【NR 定位】3GPP NR Positioning 5G定位标准解读(三)
  • 文件操作与IO(3) 文件内容的读写——数据流
  • 《PyTorch深度学习实践》第十一讲卷积神经网络进阶
  • Ansible的playbook的编写和解析
  • [环境配置]ssh连接报错“kex_exchange_identification: read: Connection reset by peer”
  • Mybatis-Plus——04,自动填充时间(新注解)
  • 【动态规划入门】最长上升子序列
  • LabVIEW眼结膜微血管采集管理系统
  • 通过GitHub探索Python爬虫技术
  • 【Python】-----基础知识
  • 如何学习、上手点云算法(二):点云处理相关开源算法库、软件、工具
  • 为什么会对猫毛过敏?如何缓解?浮毛克星—宠物空气净化器推荐
  • Linux学习-etcdctl安装
  • Qt应用软件【文件篇】读写文件技巧
  • GO常量指针
  • 微服务间通信重构与服务治理笔记
  • unity 场景烘焙中植物叶片(单面网络)出现的白面
  • 网工内推 | 国企运维,年薪最高30W,RHCE认证优先
  • WordPress排除调用某个分类下的文章
  • Java多线程——信号量Semaphore是啥