Codeforces Global Round 26 D. “a“ String Problem 【Z函数】

D. “a” String Problem

1

题意

给定一个字符串 s s s,要求把 s s s 拆分成若干段,满足以下要求:

  1. 拆分出来的每一个子段,要么是子串 t t t,要么是字符 a a a
  2. 子串 t t t 至少出现一次
  3. t ≠ " a " t \neq "a " t="a"

问有多少种不同的子串 t t t 满足以上要求

思路

如果 s s s 全是 a a a 的话,假设 ∣ s ∣ = n |s| = n s=n,那么答案是: n − 1 n - 1 n1

否则通过简单观察我们可以发现: t t t 必须包含 a a a 字符(不一定是所有,只要 t t t 可以覆盖这些非 a a a 字符即可)

假设 s s s 从左到右第一个出现非 a a a 字符的位置是 p 0 p_0 p0,如果我们先固定 t t t 的开头在 p 0 p_0 p0
我们就可以先枚举 t t t 的长度从 1 → n − p 0 + 1 1 \rarr n - p_0 + 1 1np0+1,那么如何确定当前 t t t 是否满足上述要求?

我们直接在第一个 t t t末尾后面,找第一个出现的非 a a a 字符作为第二个 t t t 的开头,然后这后面 l e n len len 个字符必须与 t t t 相等,如果相等则继续往后检查,否则当前 t t t 无效。

我们只需要预处理每一个位置后面第一个非 a a a 字符的位置就可以,倒着扫一遍就可以线性预处理出来。
匹配的过程我们可以使用 Z Z \; Z函数,这是由于本质上是从 p 0 p_0 p0 开始的字符串,拿它去和它自己本身的每个后缀做匹配,自然可以使用 Z Z \; Z 函数。
那么这个检查过程是: O ( n log ⁡ n ) O(n \log n) O(nlogn) 的(调和级数复杂度)

那么现在问题在于: t t t 不一定是以非 a a a 字符开头的。
其实这个问题很容易处理,假设我们当前有效的从 p 0 p_0 p0 开头的 ∣ t ∣ = l e n |t| = len t=len,那么我们在检查过程的同时,记录每个 t t t 的前面到前一个 t t t 的末尾,有多少个 a a a,统计这个最小值 m n mn mn
那么很显然,当前的 t t t 可以往前扩展最多 m n mn mn a a a,最后还是有效的。
那么这里的方案数就是: m n + 1 mn + 1 mn+1

所以答案最后对于每个有效长度累加即可

时间复杂度: O ( n log ⁡ n ) O(n \log n) O(nlogn)

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()const int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;typedef long long ll;std::vector<int> z_function(const std::string& s, int n){std::vector<int> z(n + 1, 0);z[1] = n;int l = 0, r = 0;fore(i, 2, n + 1){if(i <= r)	z[i] = std::min(z[i - l + 1], r - i + 1);while(i + z[i] <= n && s[1 + z[i]] == s[i + z[i]])++z[i];if(i + z[i] - 1 > r){l = i;r = i + z[i] - 1;}}return z;
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){std::string s;std::cin >> s;int n = s.size();s = '0' + s;std::vector<int> nxt_nona(n + 5, n + 5);for(int i = n; i > 0; --i){if(s[i] == 'a') nxt_nona[i] = nxt_nona[i + 1];else nxt_nona[i] = i;}if(nxt_nona[1] > n){ //全是astd::cout << n - 1 << endl;continue;}int p0 = nxt_nona[1];std::string T = s.substr(p0);T = '0' + T;auto z = z_function(T, T.size() - 1);ll ans = 0;fore(len, 1, n - p0 + 2){int mn = p0 - 1;bool ok = true;int lst = p0 + len - 1;for(int j = nxt_nona[p0 + len]; j <= n; j = nxt_nona[j + len]){if(z[j - p0 + 1] < len){ok = false;break;}mn = std::min(mn, j - lst - 1);lst = j + len - 1;}if(ok)	ans += mn + 1;}std::cout << ans << endl;}return 0; 
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

简单脉冲动画效果实现

简单脉冲动画效果实现 效果展示 CSS 知识点 CSS 变量的灵活使用CSS 动画使用 页面整体结构实现 <div class"pulse"><span style"--i: 1"></span><span style"--i: 2"></span><span style"--i: 3"…

html+CSS+js部分基础运用18

1. 按键修饰符的应用。①姓名&#xff1a;按下回车键时调用方法输出“姓名-密码”&#xff1b;②密码&#xff1a;按下shift回车时调用方法输出“姓名密码” 图1 初始效果图 图2 按键修饰符效果图 2. 仿淘宝Tab栏切换&#xff0c;熟悉…

图解Mamba——从流体力学的角度理解Mamba

1.Transformer的问题 上面是Transformer的网络结构。对于一句话的每个单词&#xff0c;都需要跟所有单词算注意力机制。因此注意力机制的计算复杂度为 O ( n 2 ) O(n^2) O(n2)&#xff0c;其中 n n n为句子的长度&#xff0c;即单词(符号)的个数。如下图所示。 所以这也是现在…

2021 hnust 湖科大 操作系统课设 报告+原代码+指导书+流程图源文件

2021 hnust 湖科大 操作系统课设 报告原代码指导书流程图源文件 详情 目录 验证类实验&#xff1a; 1 实验一&#xff1a;Windows进程管理 1 一、 实验题目&#xff1a; 1 二、 实验目的 1 三、 实验内容 1 四、 实验结果与分析 2 五、 小结与心得体会 5 实验二&#xff1a;L…

【HarmonyOS】遇见的问题汇总

一、当前编辑的页面&#xff0c;预览打不开 1、问题说明 当前编辑的页面&#xff0c;预览打不开&#xff0c;日志提示如下&#xff1a; Route information is not configured for the current page. To avoid possible redirection issues, configure route information for…

数据结构 —— 堆

1.堆的概念及结构 堆是一种特殊的树形数据结构&#xff0c;称为“二叉堆”&#xff08;binary heap&#xff09; 看它的名字也可以看出堆与二叉树有关系&#xff1a;其实堆就是一种特殊的二叉树 堆的性质&#xff1a; 堆中某个结点的值总是不大于或不小于其父结点的值&…

Vuepress 2从0-1保姆级进阶教程——标准化流程(Tailwindcss+autoprefixer+commitizen)

Vuepress 2 专栏目录【已完结】 1. 入门阶段 Vuepress 2从0-1保姆级入门教程——环境配置篇Vuepress 2从0-1保姆级入门教程——安装流程篇Vuepress 2从0-1保姆级入门教程——文档配置篇Vuepress 2从0-1保姆级入门教程——主题与部署 2.进阶阶段 Vuepress 2从0-1保姆级进阶教程—…

AM273X毫米波演示

介绍 毫米波演示展示了 AM273X SOC 使用毫米波 SDK&#xff08;软件开发工具包&#xff09;中的驱动程序的一些功能。它允许用户指定chirp配置文件并实时显示检测到的对象和其他信息。 以下是此演示功能的高级描述&#xff1a; 能够通过 UART 端口上的命令行界面 &#xff08;…

文字悬停效果

文字悬停效果 效果展示 CSS 知识点 CSS 变量使用回顾-webkit-text-stroke 属性的运用与回顾 页面整体结构实现 <ul><li style"--clr: #e6444f"><a href"#" class"text">First</a></li><li style"--cl…

苹果WWDC重磅发布的IOS 18、Apple Intelligence背后的技术分析!

2024年6月10日&#xff0c;在2024年WWDC全球开发者大会上&#xff0c;苹果推出了Apple Intelligence&#xff0c;这是深度集成到iOS 18、iPadOS 18和macOS Sequoia中的个人智能系统。 为了让大模型能在 iPhone 端侧跑&#xff0c;苹果还是做了很多事情的。接下来就跟大家介绍一…

Spring学习笔记

1 spring介绍 1)为什么学习spring ​ 1. Spring技术是JavaEE开发必备技能&#xff0c;企业开发技术选型命中率>90% ​ 2. 简化开发&#xff0c;降低企业级开发的复杂性 ​ 3. 框架整合&#xff0c;高效整合其他技术&#xff0c;提高企业级应用开发与运行效率 ​ 作为一…

IDEA创建Mybatis项目

IDEA创建Mybatis项目 第一步&#xff1a;创建库表 -- 创建数据库 create database mybatis_db;-- 使用数据库 use mybatis_db;-- 创建user表 CREATE TABLE user (id INT AUTO_INCREMENT PRIMARY KEY,username VARCHAR(50) NOT NULL,password VARCHAR(50) NOT NULL,email VARC…

Django API开发实战:前后端分离、Restful风格与DRF序列化器详解

系列文章目录 Django入门全攻略&#xff1a;从零搭建你的第一个Web项目Django ORM入门指南&#xff1a;从概念到实践&#xff0c;掌握模型创建、迁移与视图操作Django ORM实战&#xff1a;模型字段与元选项配置&#xff0c;以及链式过滤与QF查询详解Django ORM深度游&#xff…

第十五届蓝桥杯大赛 国赛 pb组F题【括号与字母】(15分) 栈的应用

博客主页&#xff1a;誓则盟约系列专栏&#xff1a;IT竞赛 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ 试题F:括号与字母 【问题描述】 给定一个仅包含小写字母和括号的字符串 S …

【CentOS 7】挑战探索:在CentOS 7上实现Python 3.9的完美部署指南

【CentOS 7】挑战探索&#xff1a;在CentOS 7上实现Python 3.9的完美部署指南 大家好 我是寸铁&#x1f44a; 总结了一篇【CentOS 7】挑战探索&#xff1a;在CentOS 7上实现Python 3.9的完美部署指南详细步骤✨ 喜欢的小伙伴可以点点关注 &#x1f49d; 前言 此篇教程只适用于p…

LeetCode 算法: 旋转图像c++

原题链接&#x1f517;&#xff1a; 旋转图像 难度&#xff1a;中等⭐️⭐️ 题目 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图…

OrangePi AIpro小试牛刀-目标检测(YoloV5s)

非常高兴参加本次香橙派AI Pro&#xff0c;香橙派联合华为昇腾打造的一款AI推理开发板评测活动&#xff0c;以前使用树莓派Raspberry Pi4B 8G版本&#xff0c;这次有幸使用国产嵌入式开发板。 一窥芳容 这款开发板搭载的芯片是和华为昇腾的Atlas 200I DK A2同款的处理器&#…

服务器通的远程桌面连接不上,服务器通的远程桌面连接不上解决方法

当面临服务器远程桌面连接不上的问题时&#xff0c;专业的处理方式需要遵循一系列步骤来确保问题得到准确且高效的解决。以下是一些建议的解决方法&#xff1a; 一、初步排查与诊断 1. 检查网络连接&#xff1a; - 确保本地计算机与服务器之间的网络连接是稳定的。 - 尝…

【万方数据库爬虫简单开发(自用)】

万方数据库爬虫简单开发&#xff08;自用&#xff09;&#xff08;一&#xff09; 使用Python爬虫实现万方数据库论文的搜索并获取信息1.获取url2.输入关键词3.使用BeautifulSoup解析4.获取文章标题信息 使用Python爬虫实现万方数据库论文的搜索并获取信息 后续会逐步探索更新…

【Mac】Downie 4 for Mac(视频download工具)兼容14系统软件介绍及安装教程

前言 Downie 每周都会更新一个版本适配视频网站&#xff0c;如果遇到视频download不了的情况&#xff0c;请搜索最新版本https://mac.shuiche.cc/search/downie。 注意&#xff1a;Downie Mac特别版不能升级&#xff0c;在设置中找到更新一列&#xff0c;把自动更新和自动downl…