算法------（13）KMP

例题：（1）AcWing 831. KMP字符串 

        。。其实写完也不太理解。。随便写点吧

        KMP就是求next数组和运用next的数组的过程。相比传统匹配模式一次更新一单位距离的慢速方法，next数组可以让下表字符串一次更新n - next【n】个距离，加快了匹配速度。next【i】记录的是某字符串的前i个字符中前缀与后缀最长的匹配长度。

        对于模版中的j，我的理解是已经匹配了j个字符，因此next【i】还可以理解为对于已经匹配了i个字符的字符串来说，假如后续匹配不成立，则该字符串至少还有next【i】个字符是匹配的。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10,M = 1e6+10;
int ne[N];
int n,m;
char p[N],s[M];
int main()
{
    cin >> n >> p+1 >> m >> s+1;
    ne[1] = 0;
    for(int i = 2,j = 0;i<=n;i++){
        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<=m;i++){
        while(j && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) j++;
        if(j == n){
            printf("%d ",i - n);
            j = ne[j];
        }
    }
    return 0;
}

练习：（1） Leetcode 459 重复的子字符串

        。。。好难啊！！！！这是easy？？？

        我们可以证明 非空字符串s可由一个子串重复多次构成 当且仅当 把两个s连接起来且去掉前面后面的各一个字符，其中仍然存在s作为新字符串的子串。 

        从前往后推很显然，从后往前推需要一定证明。显然我不会，摘抄一下Leetcode的答案。

（2） P1470 [USACO2.3] 最长前缀 Longest Prefix

         其实与KMP无关但不知道为什么加了个KMP的标签。。。没做出来。。

        跟之前做过的一些题目有些类似。dp[i]的含义为[0,i-1]个字母可以分解，因此我们枚举每一个j，只要满足[0,j-1]时能分解且[j,i-1]也在P集合内即可。对于查询[j,i-1]，由于题目说P集合内字符串长度<=10，因此我们对每一个i只需要枚举10个j即可，这样大大优化了时间。

        以及不知为什么本地跑不了。。。（问了朋友可能是文件输入输出的关系）

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
const int N = 2e5+10;
bool dp[N];
unordered_set<string> res;
int main(int argc, char** argv) {
	string ss;
	while(cin >> ss){
		if(ss == ".") break;
		res.insert(ss);
	}
	string ans = "";
	while(cin >> ss){
		ans += ss;
	}
	dp[0] = true;
	int n = ans.length();
	for(int i = 1;i<=n;i++){
		for(int j = i;j>=max(i-10,0);j--){
			if(dp[j] && (res.find(ans.substr(j,i-j))!=res.end())){
				dp[i] = true;
				continue;
			}
		}
	}
	for(int i = n;i>=0;i--){
		if(dp[i]){
			printf("%d",i);
			break;
		}
	}
	return 0;
}

(3) P3435 [POI2006] OKR-Periods of Words

        太难了太难了。。。

        一个前缀的最大周期长度就是其长度减去其最小匹配长度，也就是其最短的共同前后缀的长度。 next数组求的是最大匹配长度，而不断递归求next数组得到的正是不为0的最小匹配长度。递归处理时可以把next数组直接更新为求得的最短长度，这样求取速度会更快。

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1000010;
char str[N];
int ne[N];
int main(int argc, char** argv) {
	int n;
	scanf("%d%s",&n,str+1);
	ne[1] = 0;
	for(int i = 2,j = 0;i<=n;i++){
		while(j && str[i] != str[j+1]) j = ne[j];
		if(str[i] == str[j+1]) j++;
		ne[i] = j;
	}
	ll ans = 0;
	for(int i = 2,j = 2;i<=n;i++,j = i){
		while(ne[j]) j = ne[j];
		if(ne[i]) ne[i] = j;
		ans += i-j;
	}
	printf("%lld",ans);
	return 0;
}

(4) Leetcode 面试题17.17 多次搜索

          对每一个smalls内的字符串求next数组，然后与big字符串进行kmp匹配。注意kmp的i返回的是字符串的最后一个字符下标。以及每一次匹配都要先清空next数组。

class Solution {
    int ne[1010];
    vector<vector<int>> res;
public:
    void next(string str){
        char x[1010];
        int n = str.length();
        for(int i = 1;i<=n;i++) x[i] = str[i-1]; 
        for(int i = 2,j = 0;i<=n;i++){
            while(j && x[i] != x[j+1]) j = ne[j];
            if(x[i] == x[j+1]) j++;
            ne[i] = j;
        }
    }
    vector<int> get(string a,string b){
        char x[1010],y[1010];
        int n = a.length(),m = b.length();
        for(int i = 1;i<=n;i++) x[i] = a[i-1];
        for(int i = 1;i<=m;i++) y[i] = b[i-1];
        vector<int> ans;
        for(int i = 1,j = 0;i<=n;i++){
            while(j && x[i] != y[j+1]) j = ne[j];
            if(x[i] == y[j+1]) j++;
            if(j == m){
                ans.push_back(i-m);
                j = ne[j];
            }
        }
        return ans;
    }
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        int n = smalls.size();
        for(int i = 0;i<n;i++){
            if(smalls[i] == ""){
                res.push_back({});
                continue;
            }
            memset(ne,0,sizeof(ne));
            next(smalls[i]);
            res.push_back(get(big,smalls[i]));
        }
        return res;
    }
};

(5) Leetcode 3036 匹配模式数组的子数组数目

        做出来的第一个Hard题！虽然完全不是自己想出来的！！。。。

        把nums转化为跟pattern数组一样模式的长度为n-1的数组，此题便转化为求nums数组中有几个子数组为pattern数组，这样一来直接用kmp匹配即可。转化这一步还是挺难想到的。

class Solution {
    int x[1000100],y[1000100],ne[1000100];// x,y 1-n
public:
    int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
       int n = nums.size()-1,m = pattern.size();
       for(int i = 0;i<n;i++){
           if(nums[i] < nums[i+1]) x[i+1] = 1;
           else if(nums[i] == nums[i+1]) x[i+1] = 0;
           else x[i+1] = -1;
       } 
       for(int i = 1;i<=m;i++){
           y[i] = pattern[i-1];
       } 
       for(int i = 2,j = 0;i<=m;i++){
           while(j && y[i] != y[j+1]) j = ne[j];
           if(y[i] == y[j+1]) j++;
           ne[i] = j; 
       }
       int ans = 0;
       for(int i = 1,j = 0;i<=n;i++){
           while(j && x[i] != y[j+1]) j = ne[j];
           if(x[i] == y[j+1]) j++;
           if(j == m){
               ans++;
               j = ne[j];
           }
       }
       return ans;
    }
};

(6) Leetcode 3037.在无限流中寻找模式

         做出的第二道Hard题，想出了匹配方式但是在优化上栽了！不过还算可以！

        由于是无限流，所以每次更新就匹配一次肯定会超时，因此用vector处理，由于next数组是确定的，因此每次不用从头匹配，只需要一个一个进行匹配即可。

/**
 * Definition for an infinite stream.
 * class InfiniteStream {
 * public:
 *     InfiniteStream(vector<int> bits);
 *     int next();
 * };
 */
class Solution {
    int ne[110000];
    vector<int> p,q;
public:
    int findPattern(InfiniteStream* stream, vector<int>& pattern) {
        p.push_back(0);
        q.push_back(0);
        int r = 0,m = pattern.size();
        for(int i = 1;i<=m;i++){
            q.push_back(pattern[i-1]);
        }
        for(int i = 2,j = 0;i<=m;i++){
            while(j && q[i] != q[j+1]) j = ne[j];
            if(q[i] == q[j+1]) j++;
            ne[i] = j;
        }
        int i = 1,j = 0;
        while(1){
            p.push_back(stream->next());
            while(j && p[i] != q[j+1]) j = ne[j];
            if(p[i] == q[j+1]) j++;
            if(j == m) return i-m;
            i++;
        }
    }
};

(7) Leetcode 3008.找出数组中的美丽下标

         Hard被卡了。。

        匹配用kmp，后续查找时的优化思路为对a中每一个下标数组，在b的下标数组二分查找第一个大于等于它的数，如果这个数存在则返回其与a中对应下标的差，和其前面一个与a中对应下标的差，如果满足则返回。

class Solution {
    char p[500100],q[500100],r[500010];
    int ne1[500100],ne2[500100];
public:
    vector<int> beautifulIndices(string s, string a, string b, int k) {
        vector<int> res;
        vector<int> res1,res2;
        int n = a.length(),m = b.length(),o = s.length();
        for(int i = 1;i<=n;i++) p[i] = a[i-1];
        for(int i = 1;i<=m;i++) q[i] = b[i-1];
        for(int i = 1;i<=o;i++) r[i] = s[i-1];
        for(int i = 2,j = 0;i<=n;i++){
            while(j && p[i] != p[j+1]) j = ne1[j]; 
            if(p[i] == p[j+1]) j++; 
            ne1[i] = j;
        }
        for(int i = 2,j = 0;i<=m;i++){
            while(j && q[i] != q[j+1]) j = ne2[j]; 
            if(q[i] == q[j+1]) j++; 
            ne2[i] = j;
        }
        for(int i = 1,j = 0;i<=o;i++){
            while(j && r[i] != p[j+1]) j = ne1[j]; 
            if(r[i] == p[j+1]) j++; 
            if(j == n){
                res1.push_back(i-n);
                j = ne1[j];
            } 
        }
        for(int i = 1,j = 0;i<=o;i++){
            while(j && r[i] != q[j+1]) j = ne2[j]; 
            if(r[i] == q[j+1]) j++; 
            if(j == m){
                res2.push_back(i-m);
                j = ne2[j];
            } 
        }
        int c1 = res1.size(),c2 = res2.size();
        for (int i: res1) {
            auto it = lower_bound(res2.begin(), res2.end(), i);
            if (it != res2.end() && *it - i <= k ||
                it != res2.begin() && i - *--it <= k) {
                res.push_back(i);
            }
        }
        return res;
    }
};

（8） Leetcode 758.字符串中的加粗单词

         没啥难的。。挑错时间太长所以贴上来羞辱一下自己。。

        kmp加合并区间。首先先对words每一个字符串求next然后与s进行匹配，求出每一个需要加粗的区间。由于这些区间存在重叠而导致标签数过多，因此要求最小的标签数就需要合并区间。

class Solution {
    int ne[15];
    typedef pair<int,int> pii;
public:
    vector<pii> segs;
    vector<char> init(string x){
        vector<char> p;
        p.push_back(0);
        int n = x.length();
        for(int i = 1;i<=n;i++) p.push_back(x[i-1]);
        return p;
    }
    void next(vector<char> x){
        int n = x.size()-1;
        for(int i = 2,j = 0;i<=n;i++){
            while(j && x[i] != x[j+1]) j = ne[j];
            if(x[i] == x[j+1]) j++;
            ne[i] = j;
        }
    }
    void kmp(vector<char> x,vector<char> y){
        int n = x.size() - 1,m = y.size() - 1;
        for(int i = 1,j = 0;i<=n;i++){
            while(j && x[i] != y[j+1]) j = ne[j];
            if(x[i] == y[j+1]) j++;
            if(j == m){
                segs.push_back({i-m,i-1});
                j = ne[j];
            }
        }
    }
    string boldWords(vector<string>& words, string s) {
        int n = words.size();
        auto p = init(s);
        for(int i = 0;i<n;i++){
            memset(ne,0,sizeof(ne));
            auto q = init(words[i]);
            next(q);
            kmp(p,q);
        }
        vector<pii> res;
        sort(segs.begin(),segs.end());
        int fs = -2e9,ed = -2e9;
        for(auto seg:segs){
            int l = seg.first,r = seg.second;
            if(ed+1<l){
                if(fs!=-2e9) res.push_back({fs,ed});
                fs = l;
                ed = r;
            }
            else{
                ed = max(ed,r);
            }
        }
        if(fs!=-2e9) res.push_back({fs,ed});
        int flag = 0;
        string ans = "";
        for(auto seg:res){
            int l = seg.first,r = seg.second;
            ans += s.substr(flag,l - flag);
            ans += "<b>";
            ans += s.substr(l,r-l+1);
            ans += "</b>";
            flag = r+1;
        }
        n = s.length();
        cout <<flag;
        if(flag < n ) ans += s.substr(flag,n-flag);
        return ans;
    }
};

         

 

 

 

        

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/418677.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

三天学会阿里分布式事务框架Seata-seata事务日志mysql持久化配置

三天学会阿里分布式事务框架Seata-seata事务日志mysql持久化配置

锋哥原创的分布式事务框架Seata视频教程&#xff1a; 实战阿里分布式事务框架Seata视频教程&#xff08;无废话&#xff0c;通俗易懂版&#xff09;_哔哩哔哩_bilibili实战阿里分布式事务框架Seata视频教程&#xff08;无废话&#xff0c;通俗易懂版&#xff09;共计10条视频&…
阅读更多...
虚拟机中Linux的安装与初始化配置（更新时间24/3/1）

虚拟机中Linux的安装与初始化配置（更新时间24/3/1）

先问三个问题 vm虚拟机安装了吗&#xff1f;点击此处跳转虚拟机安装教程Linux镜像下载了吗&#xff1f;点击此处跳转Linux镜像下载教程新建Linux虚拟机配置了吗&#xff1f;点击此处跳转新建虚拟机的配置教程 顺序是&#xff1a;下载虚拟机–>下载Linux镜像–>新建Linux配…
阅读更多...
python63-Python的循环之循环使用else

python63-Python的循环之循环使用else

Python的循环都可以定义else代码块&#xff0c;当循环条件为False 时&#xff0c;程序会执行else代码块。如下代码示范了为while循环定义else代码块。 # !/usr/bin/env python# -*- coding: utf-8 -*-# Time : 2024/01# Author : Laopicount_i 0while count_i < 5:print(c…
阅读更多...
Verilog（未完待续）

Verilog（未完待续）

Verilog教程 这个教程写的很好&#xff0c;可以多看看。本篇还没整理完。 一、Verilog简介 什么是FPGA&#xff1f;一种可通过编程来修改其逻辑功能的数字集成电路&#xff08;芯片&#xff09; 与单片机的区别&#xff1f;对单片机编程并不改变其地电路的内部结构&#xff0…
阅读更多...
YOLOv9大幅度按比例减小模型计算量！加快训练！

YOLOv9大幅度按比例减小模型计算量！加快训练！

一、代码及论文链接&#xff1a; 代码链接&#xff1a;GitHub - WongKinYiu/yolov9: Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information 论文链接&#xff1a;https://github.com/WongKinYiu/yolov9/tree/main 二…
阅读更多...
Docker容器与虚拟化技术：OpenEuler 使用 docker-compose 部署 LNMP

Docker容器与虚拟化技术：OpenEuler 使用 docker-compose 部署 LNMP

目录 一、实验 1.环境 2.OpenEuler 部署 docker-compose 3.docker-compose 部署 LNMP 二、问题 1.ntpdate未找到命令 2.timedatectl 如何设置时区与时间同步 3.php网页显示时区不对 一、实验 1.环境 &#xff08;1&#xff09;主机 表1 主机 系统架构版本IP备注Lin…
阅读更多...
Visual Studio：指针和固定大小缓冲区只能在不安全的上下文中使用、 设置允许使用不安全代码（unsafe）

Visual Studio：指针和固定大小缓冲区只能在不安全的上下文中使用、 设置允许使用不安全代码（unsafe）

问题描述: 指针和固定大小缓冲区只能在不安全的上下文中使用 解决方案&#xff1a; 1、解决方案资源管理器-》选择项目-》右键-》属性 2、在生成窗口中&#xff0c;勾选“允许不安全代码” 3、再次“生成解决方案”即可
阅读更多...
C语言基础17 判断

C语言基础17 判断

断结构要求程序员指定一个或多个要评估或测试的条件&#xff0c;以及条件为真时要执行的语句&#xff08;必需的&#xff09;和条件为假时要执行的语句&#xff08;可选的&#xff09;。 C 语言把任何非零和非空的值假定为 true&#xff0c;把零或 null 假定为 false。 下面是…
阅读更多...
免费百度快速收录软件

免费百度快速收录软件

在网站SEO的过程中&#xff0c;不断更新网站内容是提升排名和吸引流量的关键之一。而对于大多数网站管理员来说&#xff0c;频繁手动更新文章并进行SEO优化可能会是一项繁琐且耗时的任务。针对这一问题&#xff0c;百度自动更新文章SEO工具应运而生&#xff0c;它能够帮助网站管…
阅读更多...
Maven面试题

Maven面试题

以下是一些关于Maven的经典面试题以及它们的答案&#xff1a; 1、什么是Maven&#xff1f; Maven是一个项目管理工具&#xff0c;用于构建、管理、发布Java项目。 2、为什么要使用Maven而不是手动管理项目依赖&#xff1f; Maven提供了依赖管理、统一的构建、打包、文档生…
阅读更多...
Unity（第二十四部）UI

Unity（第二十四部）UI

在游戏开发中&#xff0c;用户界面&#xff08;UI&#xff09;是至关重要的一部分。它负责与玩家进行交互&#xff0c;提供信息&#xff0c;并增强游戏的整体体验。Unity 提供了强大的工具和功能来创建和管理 UI。 ui的底层就是画布&#xff0c;创建画布的时候会同时创建一个事…
阅读更多...
rocketmq+rocket-dashboard win10安装部署+注册为Windows服务

rocketmq+rocket-dashboard win10安装部署+注册为Windows服务

1.1 首先去官网下载zip包 选择自己需要的版本 下载 | RocketMQ 1.2 、下载后&#xff0c;解压到指定目录 1.3、配置RocketMQ环境变量 注意&#xff0c;看对应的版本需要jdk版本 1.4、启动mqnameserver 进入bin目录下&#xff0c;双击启动mqnamesrv.cmd 启动后&#xff0c;…
阅读更多...
11-Linux部署集群准备

11-Linux部署集群准备

Linux部署集群准备 介绍 在前面&#xff0c;我们所学习安装的软件&#xff0c;都是以单机模式运行的。 后续&#xff0c;我们将要学习大数据相关的软件部署&#xff0c;所以后续我们所安装的软件服务&#xff0c;大多数都是以集群化&#xff08;多台服务器共同工作&#xff…
阅读更多...
喜报｜迪捷软件入选工信部“2023年信息技术应用创新解决方案”

喜报｜迪捷软件入选工信部“2023年信息技术应用创新解决方案”

为进一步推进信创生态建设&#xff0c;激发产业自主创新活力&#xff0c;高效促进供需协同发展&#xff0c;加强区域联动和资源整合&#xff0c;国家工业和信息化部网络安全产业发展中心&#xff08;工业和信息化部信息中心&#xff09;联合相关单位&#xff0c;遴选了一批可复…
阅读更多...
系统工程师面试问题，腾讯安卓开发面试

系统工程师面试问题，腾讯安卓开发面试

阿里面试需注意 1、面试前要做好充分的准备&#xff0c;一方面要尽可能多的搜集资料&#xff0c;对用人单位的历史、现状、规模、业务、产品、服务等方面要有所了解&#xff0c;掌握用人单位对人才的需求与使用情况&#xff1b;另一方面&#xff0c;要对照自己的实际情况&…
阅读更多...
深入理解nginx的https alpn机制

深入理解nginx的https alpn机制

目录 1. 概述2. alpn协议的简要理解2.1 ssl的握手过程2.2 通过抓包看一下alpn的细节3. nginx源码分析3.1 给ssl上下文设置alpn回调3.2 连接初始化3.3 处理alpn协议回调3.4 握手完成，启用http协议4.4 总结阅读姊妹篇：深入理解nginx的https alpn机制 1. 概述 应用层协议协商（…
阅读更多...
LabVIEW非接触式电阻抗层析成像系统

LabVIEW非接触式电阻抗层析成像系统

LabVIEW非接触式电阻抗层析成像系统 非接触式电阻抗层析成像&#xff08;NEIT&#xff09;技术以其无辐射、非接触、响应速度快的特点&#xff0c;为实时监测提供了新的解决方案。基于LabVIEW的电阻抗层析成像系统&#xff0c;实现了数据的在线采集及实时成像&#xff0c;提高…
阅读更多...
javaweb学习（day05-TomCat）

javaweb学习（day05-TomCat）

一、介绍 1 官方文档 地址: https://tomcat.apache.org/tomcat-8.0-doc/ 2 WEB 开发介绍 2.1 WEB 在英语中 web 表示网/网络资源(页面,图片,css,js)意思&#xff0c;它用于表示 WEB 服务器(主机)供浏览器访问的资源 2.2 Web 资源 WEB 服务器 ( 主机 ) 上供外界访问的 …
阅读更多...
CAPL编程学习笔记--关于on 事件的详细解释

CAPL编程学习笔记--关于on 事件的详细解释

CAPL编程是比较有特色的一种面向通讯的编程语言。 1&#xff1a;on XXX类型&#xff08;即事件类型&#xff09; 维克多的官方文档对CAPL的描述是一门类C语言&#xff0c;说白了它也是用C写出来的。我们看on&#xff08;注意都是小写&#xff09;事件的代码结构 on * { }&…
阅读更多...
Docker技术概论（2）：Docker环境的搭建

Docker技术概论（2）：Docker环境的搭建

Docker技术概论&#xff08;2&#xff09; Docker环境的搭建 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blo…
阅读更多...
最新文章

Copyright @ 2022~2023