当前位置:网站首页>[KMP] template
[KMP] template
2022-07-06 07:39:00 【Code chess】
️s
For longer strings to match
️p
It is a pattern string with small length ne[i]
: Indicates that in the pattern string i
The length of the longest common prefix with subscript as the end point j
: Always represents the end position that can match the common pre suffix
Be careful :ne[1]=0
, therefore i
from 2 Start
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
char s[N], p[N];
int ne[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
cin >> s + 1 >> p + 1;
for(int i = 2, j = 0; i <= m; i++)
{
while(j && s[i] != s[j + 1]) j = ne[j];
if(p[i] == p[j + 1]) j++;
ne[i] = j;
}
for(int i = 1, j = 0; i <= n; i++)
{
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j++;
if(j == m) j = ne[j]; // The match is successful
}
return 0;
}
边栏推荐
- Games101 Lesson 7 shading 1 Notes
- 【Redis】NoSQL数据库和redis简介
- NiO programming introduction
- Ble of Jerry [chapter]
- Oracle column to row -- a field is converted to multiple rows according to the specified separator
- Key value judgment in the cycle of TS type gymnastics, as keyword use
- OpenJudge NOI 2.1 1661:Bomb Game
- Methods for JS object to obtain attributes (. And [] methods)
- Ble of Jerry [chapter]
- TS 类型体操 之 extends,Equal,Alike 使用场景和实现对比
猜你喜欢
If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
成为优秀的TS体操高手 之 TS 类型体操前置知识储备
TS 类型体操 之 循环中的键值判断,as 关键字使用
Do you really think binary search is easy
Solution: système de surveillance vidéo intelligent de patrouille sur le chantier
Comparison of usage scenarios and implementations of extensions, equal, and like in TS type Gymnastics
Mise en œuvre du langage leecode - C - 15. Somme des trois chiffres - - - - - idées à améliorer
Three no resumes in the software testing industry. What does the enterprise use to recruit you? Shichendahai's resume
Excel的相关操作
JMeter performance test steps practical tutorial
随机推荐
TypeScript 可索引类型
实现精细化生产, MES、APS、ERP必不可少
Summary of Digital IC design written examination questions (I)
word删除括号里内容
QT color is converted to string and uint
Full Score composition generator: living on code
Le chemin du navigateur Edge obtient
Relevant introduction of clip image
Excel的相关操作
When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
Wonderful use of TS type gymnastics string
Significance and measures of encryption protection for intelligent terminal equipment
TypeScript 变量作用域
How can word delete English only and keep Chinese or delete Chinese and keep English
1015 reversible primes (20 points) prime d-ary
Cf1036c class numbers solution
Méthode d'obtention des propriétés de l'objet JS (.Et [] méthodes)
MES, APS and ERP are essential to realize fine production
js對象獲取屬性的方法(.和[]方式)
Basics of reptile - Scratch reptile