kmp算法模板(acwing831)

这篇具有很好参考价值的文章主要介绍了kmp算法模板(acwing831)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
using namespace std;
#define LL long long 
using ull = unsigned long long;
const LL N = 1e6 + 5, mod = 1e9 + 7;
char p[N], s[N];//p为子串,s为主串
int ne[N],n,m;//ne是next数组,存最大相同前后缀
int main() {
    cin >> m;
    cin >> p + 1;
    cin >> n;
    cin >> s + 1;
    for (int i = 2, j = 0; i <= m; i++)//求next数组
    {  
        while (j&&p[i] != p[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)
        { 
            printf("%d ", i - j);
        }
    }
    return 0;
}文章来源地址https://www.toymoban.com/news/detail-725821.html

到了这里,关于kmp算法模板(acwing831)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [数据结构] 串与KMP算法详解

    今天是农历大年初三,祝大家新年快乐! 尽管新旧交替只是一个瞬间,在大家互祝新年快乐的瞬间,在时钟倒计时数到零的瞬间,在烟花在黑色幕布绽放的瞬间,在心底默默许下愿望的瞬间……跨入新的一年,并不意味了一切都会朝着更美好,也没有什么会从天而降,我们赋

    2024年02月19日
    浏览(41)
  • 【数据结构】朴素模式匹配 & KMP算法

    🌈 自在飞花轻似梦,无边丝雨细如愁 🌈   🌟 正式开始学习数据结构啦~此专栏作为学习过程中的记录 🌟 子串的定位操作通常称为串的模式匹配,它求的是模式串在主串中的位置,而朴素模式匹配就是一种不断移动主串指针,每一次都和模式串依次进行比较的暴力求解方法

    2024年02月16日
    浏览(45)
  • 数据结构--字符串的KMP算法

    朴素模式匹配算法: 一旦发现当前这个子串中某个字符不匹配,就只能转而匹配下一个子串(从头开始) 但我们可以知道: 不匹配的字符之前,一定是和模式串一致的 color{red}不匹配的字符之前,一定是和模式串一致的 不匹配的字符之前,一定是和模式串一致的 我们可以利用

    2024年02月12日
    浏览(64)
  • 数据结构—串的详细解释(含KMP算法)

    1.1串的定义 串:串是由零个或多个字符组成的有限序列,又叫字符串(其的存储结构包含顺序表存储、单链表存储的形式。) 一般记为s=\\\"a1a2a3....an\\\"(n=0),其中,s是串的名称,用双引号(也可以使用单引号)括起来的字符序列是串的值,注意引号不是串的内容。ai(i=i=n)可以是字母、

    2023年04月09日
    浏览(45)
  • 【夜深人静学数据结构与算法 | 第一篇】KMP算法

    目录  前言:  KMP算法简介: 引入概念: 前缀后缀 前缀表: 简单例子: 暴力遍历: KMP算法:​  KMP算法难点: 总结: 本篇我们将详细的从理论层面介绍一下什么是KMP算法,相对应的力扣刷题专栏里也会有相对应的习题,欢迎各位前往阅读。           KMP算法是一种字符

    2024年02月08日
    浏览(70)
  • (C语言)数据结构算法-病毒感染检测(BF算法&&KMP算法)

    病毒感染检测: 医学研究者最近发现了某些新病毒,得知它们的DNA序列都是环状的。为了快速检测出患者是否感染了相应的病毒,研究者将患者的DNA和病毒的DNA均表示成一些字母组成的字符串序列,然后检测某种病毒DNA序列是否在患者的DNA序列中出现过,如果出现过,则此人

    2024年02月08日
    浏览(49)
  • 《数据结构》实验报告四:串的模式匹配(BF算法、KMP算法)

    1、了解 串 的基本概念。 2、掌握 串的模式匹配算法 的实现 。 说明以下概念 1、模式匹配:          串的模式匹配就是 子串的定位运算 。          设有两个字符串 S 和 T ,S为 主串(正文串) ,T为 子串(模式串) 。在主串S中查找与模式串T相匹配的子串,若匹配成功,确定

    2024年02月01日
    浏览(58)
  • 数据结构-串-KMP算法详解(Next数组计算)(简单易懂)

    本文章就专讲kmp,暴力匹配就不讲了(我相信能搜索kmp的,暴力匹配算法应该也都了解过了) 为什么网上那么多讲kmp 我还发文章,很多文章我觉得讲的不是太通俗易懂,大多数我看起来都觉得有些懵逼 提示:以下信息来源百度 KMP算法是一种改进的字符串匹配算法,由D.E.K

    2024年02月06日
    浏览(46)
  • 【数据结构】字符串匹配|BF算法|KMP算法|next数组的优化

    字符串匹配算法是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目,本文主要介绍BF算法(最好想到的算法,也最好实现)和KMP算法(最经典的) BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符与模式串T的第一

    2024年02月04日
    浏览(57)
  • 【AcWing算法基础课】第二章 数据结构(部分待更)

    本专栏文章为本人AcWing算法基础课的学习笔记,课程地址在这。如有侵权,立即删除。 邻接表 :存储图和树 e数组存储每个结点的值,ne数组存储每个结点的指向的下一个结点。 数组模拟链表比较快,指针模拟会涉及到new操作,比较慢。 题目链接 :826. 单链表 1.1题目描述

    2024年02月13日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包