codeforces 1200E

news/2024/2/28 11:10:06

c f cf cf上的题就是不板,综合考察对 k m p kmp kmp的运用
题目链接

题目大意

给定 n n n个字符串,从左到右依次把两个字符串合成一个,每两个合并的字符串,需要你找到最大的 i i i,满足前字符串长度为 i i i的后缀等于后字符串长度为 i i i的前缀,把后字符串第 i i i位以后的字符接到前字符串上,若没有相同的前后缀则直接拼接,输出最终结果

思路

题目要求找到相同的前缀和后缀,立刻想到要用 k m p kmp kmp,但是 k m p kmp kmp是在一个字符串内用的,所以每到两个字符串要链接时,我们先构造一个合起来的字符串 s s s,对合起来的字符串进行 g e t get get_ p m t pmt pmt,找到失配数组 p m t pmt pmt,要找的相同的前后缀数量就是 p m t [ s . s i z e ( ) − 1 ] pmt[s.size()-1] pmt[s.size()1],注意一点:为了防止越过过度匹配超过自身长度,我们要在两个要链接的字符串中加一段乱码,如匹配 101 101 101 010 010 010

ACcode

#include<bits/stdc++.h>using namespace std;const int M = 1e6 + 9;
int pmt[M];void get_pmt(const string& p) {pmt[0] = 0;pmt[1] = 0;for (int i = 1, j = 0;i < p.size();i++) {while (j && p[i] != p[j])j = pmt[j - 1];if (p[i] == p[j])j++;pmt[i] = j;}
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin >> n;string ans;cin >> ans;string s;//cout << n << ' ' << ans;for (int i = 2;i <= n;i++) {cin >> s;int len = min(s.size(), ans.size());string ss = s + "(@#$%^&*!~~?><" + ans.substr(ans.size() - len, len);get_pmt(ss);//cout << ss << '\n';for (int j = pmt[ss.size() - 1];j < s.size();j++) ans += s[j];}cout << ans << '\n';return 0;
}

http://www.ppmy.cn/news/1350386.html

相关文章

Python 3 时间序列可视化指南

简介 时间序列分析属于统计学的一个分支&#xff0c;涉及对有序的、通常是时间性的数据进行研究。当适当应用时&#xff0c;时间序列分析可以揭示意想不到的趋势&#xff0c;提取有用的统计数据&#xff0c;甚至预测未来的趋势。因此&#xff0c;它被应用于许多领域&#xff0…

代码随想录算法训练营day 29|第七章 回溯算法part05

491.递增子序列 本题和大家刚做过的 90.子集II 非常像&#xff0c;但又很不一样&#xff0c;很容易掉坑里。 代码随想录 视频讲解&#xff1a;回溯算法精讲&#xff0c;树层去重与树枝去重 | LeetCode&#xff1a;491.递增子序列_哔哩哔哩_bilibili 这道题本身没那么难想到,但…

unity2017 遇到visual studio 2017(社区版) 30日试用期到了

安装unity2017 遇到visual studio 2017 30日试用期到了&#xff0c;网上百度搜了好多方法都没有成功。 最后用了这个方法&#xff1a; 1)启动vs2017&#xff0c;在弹出要登录的窗口之前&#xff0c;迅速的点击工具-》选项-》账户&#xff0c;勾选在添加账户或对账户重新进行身…

〔025〕Stable Diffusion 之 接口开发 篇

✨ 目录 ▷ 启动接口▷ 接口文档▷ 接口开发▷ 代码解释 ▷ 启动接口 想要在各种其他服务中对接 Stable Diffusion 的绘画功能&#xff0c;需要开启 Stable Diffusion 的 api 功能开发接口需要有一定的技术功底才可以&#xff0c;非技术人员其实不用学习直接在 webui-user.bat…

【Java程序设计】【C00264】基于Springboot的原创歌曲分享平台(有论文)

基于Springboot的原创歌曲分享平台&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的原创歌曲分享平台 本系统分为平台功能模块、管理员功能模块以及用户功能模块。 平台功能模块&#xff1a;在平台首页可以查看首…

分布式系统架构介绍

1、为什么需要分布式架构&#xff1f; 增大系统容量&#xff1a;单台系统的性能瓶颈&#xff0c;多台机器才能应对大规模的应用场景&#xff0c;所以就需要我们的应用支撑平台具备分布式架构。 加强系统的可用&#xff1a;为了满足业务的SLA要求&#xff0c;需要通过分布式架构…

【LeetCode】37. 解数独(困难)——代码随想录算法训练营Day30

题目链接&#xff1a;37. 解数独 题目描述 编写一个程序&#xff0c;通过填充空格来解决数独问题。 数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&…

C++泛型编程:模板偏特化

模板偏特化为模板提供特殊的实现&#xff0c;针对特定的模板参数或参数组合。 在模板全特化&#xff0c;所有的模板参数都被指定了具体的类型。 我们可以在泛化设计中提供一个特化版本&#xff0c;针对其中某个或者数个模板参数进行特化&#xff0c;我们可以指定一部分模板参…

STM32自学☞定时器定时中断案例

timer_interrupt.c文件 /* 初始化函数编写步骤&#xff1a; 1.打开时钟 2.选择时基单元的时钟源&#xff08;内部时钟源&#xff09; 3.配置时基单元 4.NVIC配置 5.启动定时器 */ #include "stm32f10x.h" #include "stm32f10x_tim.h" #include …

​​​​​​C#系列-C#EF框架实现分库分表(21)

在C#中使用Entity Framework (EF)框架实现分库分表&#xff08;也称为数据库分片或水平切分&#xff09;是一个相对复杂的过程&#xff0c;因为EF本身并不直接支持分库分表。分库分表通常是为了解决单一数据库的性能瓶颈、数据量过大、高并发等问题而采取的一种策略。 实现分库…

速盾:cdn集群防御空间dns服务器

在当今数字化时代&#xff0c;网络安全和性能成为了企业关注的焦点。速盾的CDN集群防御空间DNS服务器技术为网站提供了更高水平的安全性和性能优化。本文将深入探讨这一技术的关键特点和优势。 1. 集群防御&#xff1a; 速盾的CDN集群防御通过分布在全球的节点集群&#xff0c;…

【Python】单元测试unittest框架

note 使用unittest框架进行单元测试是Python标准库的一部分&#xff0c;提供了编写测试用例、测试套件以及运行测试的能力。测试用例是继承自unittest.TestCase的类。在这个类中&#xff0c;你可以定义一系列的方法来测试不同的行为。每个测试方法都应该以test开头。 文章目录…

华为配置车地通信快速切换实验

配置车地通信快速切换示例 组网图形 图1 配置车地通信快速切换业务示意图 组网需求配置思路配置注意事项操作步骤配置文件 组网需求 某轨交企业为了降低网络部署成本&#xff0c;提升服务质量&#xff0c;希望通过WLAN技术实现车地通信&#xff0c;使部署在地面网络的组播服务器…

已解决org.springframework.web.HttpMediaTypeNotAcceptableException异常的正确解决方法,亲测有效!!!

已解决org.springframework.web.HttpMediaTypeNotAcceptableException异常的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 文章目录 问题分析 报错原因 解决思路 解决方法 总结 问题分析 在Spring MVC应用中处理HTTP请求时&#xff0c;我们有…

JavaI/O流 File类(文件)

目录 File类实例 File类 Java的File类是java.io.File的一个类&#xff0c;它表示文件或目录的路径名。这个类在处理文件和目录时非常有用&#xff0c;它提供了很多静态方法来操作文件和目录。 以下是一些File类的常见方法&#xff1a; 构造方法&#xff1a;创建表示文件或目…

洛谷: P1308 [NOIP2011 普及组] 统计单词数

前言: 这道题没理解清题目表达意思&#xff0c;我开始想的是用map来记录个数&#xff0c;然后一个变量记录一开始出现的单词位置&#xff0c;不挺简单的吗&#xff0c;然后....就AC了2个..从错误提示能看到个数没啥问题&#xff0c;但是第一个单词位置不对&#xff0c;看了新样…

【原创 附源码】Flutter安卓及iOS海外登录--Google登录最详细流程

最近接触了几个海外登录的平台&#xff0c;踩了很多坑&#xff0c;也总结了很多东西&#xff0c;决定记录下来给路过的兄弟坐个参考&#xff0c;也留着以后留着回顾。更新时间为2024年2月8日&#xff0c;后续集成方式可能会有变动&#xff0c;所以目前的集成流程仅供参考&#…

三、案例 - MySQL数据迁移至ClickHouse

MySQL数据迁移至ClickHouse 一、生成测试数据表和数据1.在MySQL创建数据表和数据2.在ClickHouse创建数据表 二、生成模板文件1.模板文件内容2.模板文件参数详解2.1 全局设置2.2 数据读取&#xff08;Reader&#xff09;2.3 数据写入&#xff08;Writer&#xff09;2.4 性能设置…

15 ABC基于状态机的按键消抖原理与状态转移图

1. 基于状态机的按键消抖 1.1 什么是按键&#xff1f; 从按键结构图10-1可知&#xff0c;按键按下时&#xff0c;接点&#xff08;端子&#xff09;与导线接通&#xff0c;松开时&#xff0c;由于弹簧的反作用力&#xff0c;接点&#xff08;端子&#xff09;与导线断开。 从…

Linux操作系统基础(三):虚拟机与Linux系统安装

文章目录 虚拟机与Linux系统安装 一、系统的安装方式 二、虚拟机概念 三、虚拟机的安装 四、Linux系统安装 1、解压人工智能虚拟机 2、找到解压目录中的node1.vmx 3、启动操作系统 虚拟机与Linux系统安装 一、系统的安装方式 Linux操作系统也有两种安装方式&#xf…
最新文章