当前位置：首页 > news >正文

【马拉车 KMP 差分数组】P6216 回文匹配|省选-

news 来源：原创 2025/8/28 9:14:10

本文涉及知识点

较难理解的字符串查找算法KMP
C++差分数组
马拉车算法

P6216 回文匹配

题目描述

对于一对字符串 $s_1,s_2)$ ，若 $s_1$ 的长度为奇数的子串 $(l, r)$ 满足 $(l, r)$ 是回文的，那么 $s_1$ 的“分数”会增加 $s_2$ 在 $(l, r)$ 中出现的次数。

现在给出一对 $s_1,s_2)$ ，请计算出 $s_1$ 的“分数”。

答案对 $2 ^ {32}$ 取模。

输入格式

第一行两个整数， $n, m$ ，表示 $s_1$ 的长度和 $s_2$ 的长度。

第二行两个字符串， $s_1,s_2$ 。

输出格式

一行一个整数，表示 $s_1$ 的分数。

输入输出样例 #1

输入 #1

10 2
ccbccbbcbb bc

输出 #1

输入输出样例 #2

输入 #2

20 2
cbcaacabcbacbbabacca ba

输出 #2

说明/提示

【样例解释】

对于样例一：

子串 $(1, 5)$ 中 $s_2$ 出现了一次，子串 $(2, 4)$ 中 $s_2$ 出现了一次。

子串 $(7, 9)$ 中 $s_2$ 出现了一次，子串 $(6, 10)$ 中 $s_2$ 出现了一次。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据： $\le n,m \le 3 \times 10 ^ 6$ ，字符串中的字符都是小写字母。

详细的数据范围：

Subtask 编号	$\le$	分值
$1$	$100$	$15$
$2$	$10 ^ 3$	$15$
$3$	$\times 10 ^ 3$	$20$
$4$	$\times 10 ^ 5$	$30$
$5$	$\times 10 ^ 6$	$20$

马拉车算法扩展KMP 2次差分数组

马拉车算法在O(n)时间内计算出，所有奇数回文的中心和最大半长。
s3=s2+s1，m2 = |s2|。z函数在O(n)是内计算出s1[i1 $\sim$ i1+m2-1]是否是s2。用a[i]记录此值。
回文s1[left $\sim$ r]对结果的贡献是：
a[left…r-m2+1]之和，这样的总时间复杂度是O(nn)。
x1 = r - m2 +1
用差分数组记录diff[left]++ diff[x1+1]-- 。diff的前缀和是preSum,preSum[i]就是a的数量。
单独考虑同一个中心的回文：
diff[left]++ diff[x1+1]–
diff[left+1]++ diff[x1-1+1]–
$\vdots$
即： diff[left+i]++ diff[x1+1-i ]–。i>=0 x1+1-i > left+i 即2i < x1+1-left
即 i < (x1+1-left+1)/2 ,令x2 = (x1+1-left+1)/2
diff[left]到diff[left+x2] 可以再次用差分数组 diff2[left]++ diff2[left+x2]-- 。diff2的前缀和就是diff。
diff[x1+1-(x2-1)]到diff[x1+1]–，diff2[x1+1-x2+1]-- diff2[x1+1+1]++

单元测试

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;scanf("%d", &n);vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class KMPEx
{
public:static vector<int> ZFunction(string s) {int n = (int)s.length();vector<int> z(n);z[0] = n;for (int i = 1, left = 0, r = 0; i < n; ++i) {if (i <= r) {//如果此if,r-i+1可能为负数z[i] = min(z[i - left], r - i + 1);}while ((i + z[i] < n) && (s[z[i]] == s[i + z[i]])) {z[i]++;}if (i + z[i] - 1 > r) left = i, r = i + z[i] - 1;}return z;//z[i] 表示S与其后缀S[i,n]的最长公共前缀(LCP)的长度}static int MinCyc(const string& str, int unit = 1) {const int N = str.length();auto z = ZFunction(str);auto Is = [&](int k) {for (int i = k; i < N; i <<= 1) {if (z[i] < min(N - i, i)) { return false; }}return true;};for (int k = unit; k < N; k += unit) { if (Is(k))return k; }return N;}};class CPalindrome
{
public:void  CalCenterHalfLen(const string& s){vector<char> v = { '*' };for (const auto& ch : s){v.emplace_back(ch);v.emplace_back('*');}const int len = v.size();vector<int> vHalfLen(len);int center = -1, r = -1;//center是对称中心,r是其右边界（闭）for (int i = 0; i < len; i++){int tmp = 1;if (i <= r){int pre = center - (i - center);tmp = min(vHalfLen[pre], r - i + 1);}for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);vHalfLen[i] = --tmp;const int iNewR = i + tmp - 1;if (iNewR > r){r = iNewR;center = i;}}m_vOddCenterHalfLen.resize(s.length());m_vEvenCenterHalfLen.resize(s.length());for (int i = 1; i < len; i++){const int center = (i - 1) / 2;const int iHalfLen = vHalfLen[i] / 2;if (i & 1){//原字符串奇数长度m_vOddCenterHalfLen[center] = iHalfLen;}else{m_vEvenCenterHalfLen[center] = iHalfLen;}}}/// <summary>/// 获取所有回文子串，左闭右开空间/// </summary>/// <param name="s">ret[i]升序。ret[i]如果包括j，则s[i...j-1]是回文</param>/// <returns></returns>vector<vector<int>> CalLeftRightExinc(const string& s){vector<vector<int>> ret(s.length());CalCenterHalfLen(s);for (int i = 0; i < m_vOddCenterHalfLen.size(); i++) {{const int& lenMax = m_vOddCenterHalfLen[i];for (int len = 1; len <= lenMax; len++) {ret[i - len + 1].emplace_back(i + len);}}{//不能循环两次，否则结果不一定升序const int& lenMax = m_vEvenCenterHalfLen[i];for (int len = 1; len <= lenMax; len++) {ret[i - len + 1].emplace_back(i + 1 + len);}}}return ret;}vector<int> m_vOddCenterHalfLen, m_vEvenCenterHalfLen;//vOddHalfLen[i]表示 以s[i]为中心，且长度为奇数的最长回文的半长，包括s[i]//比如："aba" vOddHalfLen[1]为2 "abba" vEvenHalfLen[1]为2
};class Solution {
public:unsigned int Ans(const string& s1, const string& s2) {const int N = s1.length(), M = s2.length();CPalindrome pal;pal.CalCenterHalfLen(s1);auto s3 = s2 + s1;auto z = KMPEx::ZFunction(s3);vector<int> diff(N + 10), diff2(N + 10);for (int i = 0; i < N; i++){const int left = i - pal.m_vOddCenterHalfLen[i] + 1;const int r = i + pal.m_vOddCenterHalfLen[i] - 1;const int x1 = r - M + 1;if (x1 < left) { continue; }const auto x2 = (x1 + 1 - left + 1) / 2;diff2[left]++; diff2[left + x2]--;diff2[x1 + 1 - (x2 - 1)]--; diff2[x1 + 1 + 1]++;}int sum = 0;for (int i = 0; i < N; i++){sum += diff2[i];diff[i] = sum;}long long sum2 = 0;unsigned int ans = 0;for (int i = 0; i < N; i++){sum2 += diff[i];if (z[M + i] >= M) {ans += sum2;}}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0);int n,m; string s1,s2;cin >> n >> m >> s1 >> s2 ;		
#ifdef _DEBUG		//printf("n=%d", n);//Out(ope, "edge=");//Out(ope, ",ope=");//Out(edge2, ",edge2=");/*Out(que, "que=");*/
#endif // DEBUG	auto res = Solution().Ans(s1,s2);cout << res;return 0;
}

单元测试

TEST_METHOD(TestMethod1){auto res = Solution().Ans("ccbccbbcbb","bc");AssertEx(4u, res);}TEST_METHOD(TestMethod2){auto res = Solution().Ans("cbcaacabcbacbbabacca", "bc");AssertEx(4u, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

【马拉车 KMP 差分数组】P6216 回文匹配|省选-

本文涉及知识点较难理解的字符串查找算法KMP C差分数组马拉车算法 P6216 回文匹配题目描述对于一对字符串 ( s 1 , s 2 ) (s_1,s_2) (s1,s2)，若 s 1 s_1 s1 的长度为奇数的子串 ( l , r ) (l,r) (l,r) 满足 ( l , r ) (l,r) (l,r) 是回文的&#…...

编程日记 2025/8/28 9:14:10

C/C++测试框架googletest使用示例

文章目录文档编译安装示例参考文章文档 https://github.com/google/googletest https://google.github.io/googletest/ 编译安装 googletest是cmake项目，可以用cmake指令编译 cmake -B build && cmake --build build将编译产物lib和include 两个文件夹…...

编程日记 2025/8/28 9:07:11

提高MCU的效率方法

要提高MCU（微控制器单元）的编程效率，需要从硬件特性、代码优化、算法选择、资源管理等多方面入手。以下是一些关键策略： 1. 硬件相关优化时钟与频率：根据需求选择合适的时钟源（内部/外部振荡器），避免过高的时钟频率导致功耗浪费。关闭未使用的外设时钟（如定时器、UA…...

编程日记 2025/8/28 4:02:03

Ansible 实战：Roles，运维的 “魔法函数”

一、介绍你现在已经学过tasks和handlers，那么，最好的playbook组织方式是什么呢？答案很简单：使用roles！roles基于一种已知的文件结构，能够自动加载特定的vars_files、tasks以及handlers。通过roles对内容进…...

编程日记 2025/8/28 9:06:50

GO简单开发grpc

什么是grpc 首先我们需要了解，什么是grpc gRPC（全称：google remote procedure call）是由Google开发的一个高性能、开源的远程过程调用（RPC）框架。它基于 HTTP/2 协议，并且使用 Protocol Buffer…...

编程日记 2025/8/28 9:07:10

强引用，弱引用，软引用，虚引用，自旋锁，读写锁

强引用：强引用GC不会回收软引用：内存够的话不回收，内存不够的话回收弱引用：不管内存够不够，只要有GC就回收虚引用：点get是null，但是GC后他会把引用放到引用队列里边自旋锁：是指尝…...

编程日记 2025/8/27 16:47:44

C++异常处理 throw try catch

C 异常处理概述 C 异常处理机制提供了一种在程序运行时捕获错误或异常情况的方式。异常处理的目的是使得程序在遇到错误时能够优雅地终止或恢复，并防止程序出现崩溃。C 使用 try, throw, 和 catch 关键字来实现异常处理。异常处理的基本结构： throw: …...

编程日记 2025/8/27 8:45:28

优化 Web 性能：管理第三方资源（Third-Party Summary）

在现代 Web 开发中，第三方资源（如分析工具、广告脚本、字体服务）为网站提供了丰富的功能，但也可能成为性能瓶颈。Google 的 Lighthouse 工具在性能审计中提供了“第三方资源概要”（Third-Party Summary）&am…...

编程日记 2025/8/28 9:06:49

第六章、系统级 I/O

真题考点考点一：Unix I/O 所有的 I/O 设备(例如网络、磁盘和终端)都被模型化为文件，而所有的输入和输出都被当作对相应文件的读和写来执行。这种将设备优雅地映射为文件的方式，允许 Linux 内核引出一个简单、低级的应用接口，称为…...

编程日记 2025/8/25 8:21:39

Jetpack Compose 自定义标题栏终极指南：从基础到高级实战

Jetpack Compose 自定义标题栏终极指南：从基础到高级实战本文将带你彻底掌握 Compose 标题栏开发，涵盖 5 种专业级实现方案性能优化技巧完整可运行代码。 📚 核心方案对比方案特点适用场景复杂度基础Row布局完全自定义，灵…...

编程日记 2025/8/27 0:13:36

晶晨S905-S905L-S905LB_S905M2通刷_安卓6.0.1_16S极速开机_线刷固件包

晶晨S905-S905L-S905LB_S905M2通刷_安卓6.0.1_16S极速开机_线刷固件包线刷方法：（新手参考借鉴一下） 刷机工具版本请用2.2.0以上，导入固件后，刷机工具右侧两个擦除打勾，然后点开始。插上刷机神器&#xf…...

编程日记 2025/8/23 7:21:07

tkiner模块的初步学习

文章目录一、前言二、概念2.1 安装2.2 窗口三、小部件3.1 概述3.2 常用小部件3.2.1 Label3.2.2 Button3.2.3 Entry3.2.4 Text3.2.5 Listbox3.2.6 Checkbutton3.2.7 Radiobutton3.2.8 Scrollbar 3.3 更多小部件3.3.1 Scale3.3.2 Spinbox3.3.3. Progressbar 3.4 主题小部件四、…...

编程日记 2025/8/22 7:57:40

Java常用数据结构操作方法全面总结

目录一、List接口及其实现类二、Set接口及其实现类三、Map接口及其实现类四、Queue/Deque队列五、Stack栈六、树形结构七、注意事项与最佳实践总结一、List接口及其实现类核心实现类 ArrayList：基于动态数组LinkedList：基于双向链表常用操作方法…...

编程日记 2025/8/22 2:28:57

Java的Selenium的特殊元素操作与定位之select下拉框

如果页面元素是一个下拉框，我们可以将此web元素封装为Select对象 Select selectnew Select(WebElement element); Select对象常用api select.getOptions();//获取所有选项select.selectBylndex(index);//根据索引选中对应的元素select.selectByValue(value);//选…...

编程日记 2025/8/18 0:00:07

STM32单片机入门学习——第15节: [6-3] TIM输出比较

写这个文章是用来学习的,记录一下我的学习过程。希望我能一直坚持下去,我只是一个小白,只是想好好学习,我知道这会很难，但我还是想去做！ 本文写于：2025.04.05 STM32开发板学习——第15节: [6-3] TIM输出比较前言开发板说明引用解答和科普一…...

编程日记 2025/8/22 12:04:18

力扣经典算法篇-9-跳跃游戏（贪心算法，反向递推）

题干： 给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。示例 …...

编程日记 2025/8/22 2:28:57

java面向对象 - 封装、继承和多态

1.封装定义封装是把对象的属性和操作（或服务）结合为一个独立的整体，并尽可能隐藏对象的内部实现细节。通过访问控制修饰符（如private、protected、public）对属性和方法的访问进行限制，以此提升代码的安全性与可维护性。要点访问控制：运用private修饰属性，防止外部直…...

编程日记 2025/8/28 9:09:28

铁电液晶（FLC）与反铁电液晶（AFLC）

### **铁电液晶（FLC）与反铁电液晶（AFLC）的原理、区别及应用** --- ## **1. 基本原理** ### **（1）铁电液晶（Ferroelectric Liquid Crystal, FLC）** - **分子结构**： …...

编程日记 2025/8/27 4:34:26

经典算法 a^b

原题目链接问题描述求 a 的 b 次方对 p 取模的值，即计算： a^b mod p输入格式输入一行，包含三个整数 a、b 和 p，中间用空格隔开。输出格式输出一个整数，表示 a^b mod p 的值。数据范围 0 ≤ a, b ≤ 10^91 …...

编程日记 2025/8/28 9:11:49

Python解决“组成字符串ku的最大次数”问题

Python解决“组成字符串ku的最大次数”问题问题描述测试样例解题思路代码问题描述给定一个字符串 s，该字符串中只包含英文大小写字母。你需要计算从字符串中最多能组成多少个字符串 “ku”。每次可以随机从字符串中选一个字符，并且选中的字符不能再使…...

编程日记 2025/8/23 5:12:43

ubuntu22使用TrinityCore搭建魔兽世界服务器

目录一、Ubuntu22工具下载二、服务端编译配置1. 从 git 上拉取服务端代码2. 编译客户端3. 修改配置文件4. 加载sql语句5. 下载客户端6. 下载必要sql文件三、客户端连接配置四、游戏启动一、Ubuntu22工具下载下载所有需要的工具 sudo apt-get update sudo apt-get install…...

编程日记 2025/8/27 6:33:27

LeetCode - 739.每日温度问题单调栈解法

目录问题描述方法思路：单调栈核心思想为什么用单调栈？ 算法步骤代码实现与逐行解析示例解析复杂度分析总结问题描述给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answe…...

编程日记 2025/8/28 9:11:47

GESP:2025-3月等级8-T1-上学

时间限制 : 1 秒内存限制 : 128 MB C 城可以视为由 n个结点与 m条边组成的无向图。这些结点依次以1,2,....n标号，边依次以 1,2...m标号。第i条边（1<i<m ）连接编号为ui 与vi的结点，长度为li米。小 A 的学校坐落在 C 城中…...

编程日记 2025/8/27 18:53:09

宏碁笔记本电脑擎7PRO搭载的 NVIDIA RTX 5080 显卡安装pytorch

宏碁笔记本电脑擎7PRO搭载的 NVIDIA RTX 5080 显卡是一款高性能移动 GPU，基于 NVIDIA 最新的 Blackwell 架构设计，通过修正架构（Blackwell）、显存类型与带宽（GDDR7、960GB/s）、Tensor Core 与 RT Core 全面…...

编程日记 2025/8/28 9:11:48

Qwen-7B-Chat 本地化部署使用

通义千问简介通义千问是阿里云推出的超大规模语言模型，以下是其优缺点： 优点强大的基础能力：具备语义理解与抽取、闲聊、上下文对话、生成与创作、知识与百科、代码、逻辑与推理、计算、角色扮演等多种能力。可以续写小说、编写邮件、解…...

编程日记 2025/8/28 4:36:51

数据结构，顺序存储线性表

//线性表顺序存储 #include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 #define ElemType int //定义结构体 typedef struct LinearList{ElemType elem[MAXSIZE];int last; }LinearList; //初始化链表 void InitList(LinearList &L){L.last-1; };…...

编程日记 2025/8/22 19:39:17

Matlab轴承故障信号仿真与故障分析

1.摘要本文介绍了一个基于Matlab的轴承故障信号仿真与分析程序，旨在模拟和分析轴承内圈故障信号的特征。程序首先通过生成故障信号、共振信号和调制信号，添加噪声和离散化处理，构建模拟的振动信号，并保存相关数据。通过快速傅里…...

编程日记 2025/8/28 4:13:59

Git三剑客：工作区、暂存区、版本库深度解析

一、引言：为什么需要理解Git的核心区域？ 作为开发者，Git是日常必备的版本控制工具。但你是否曾因以下问题感到困惑？ 修改了文件，但 git status 显示一片混乱？ git add 和 git commit 到底做了什么&#x…...

编程日记 2025/8/28 9:07:09

stack和queue

1.stack的使用函数说明接口说明 stack() 构造空的栈 empty 检测stack是否为空 size 返回stack中元素的个数 top 返回栈顶元素的引用 push 将元素val压入stack中 pop 将stack中尾部的元素弹出 void test_stack() {stack<int> st;st.push(1);st.push(2);st.push(3);s…...

编程日记 2025/8/23 5:11:22

【补题】Codeforces Round 1011 (Div. 2) C. Serval and The Formula

题意：给两个数，问你存不存在k使nmn异或m 思路： 为了让nmn异或m成功，很明显有两个数在同一位上最多只能有1个1。因为如果有两个就会导致数字变小，很明显nm是不可能成功的，因为你怎么搞都会有至少一个一模一…...

编程日记 2025/8/28 9:04:25

基于javaweb的SpringBoot汉服文化bbs系统设计与实现(源码+文档+部署讲解）

技术范围：SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。主要内容：免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...

编程日记 2025/8/22 5:12:45

Vision_Robot

import time import tkinter as tk from tkinter import messagebox from PIL import Image, ImageTk import socket import threading from datetime import datetime import logging import subprocess # 确保导入 subprocess 库 import os import pyautogu…...

编程日记 2025/8/22 4:49:11

爬虫练习案例

案例1： 爬取菜鸟教程左侧导航栏的分类内容： 在pycharm中书写代码。先倒入相关模块。 import requests from bs4 import BeautifulSoup import lxml.etree as le这个案例写两种写法。第一种： urlhttps://www.runoob.com/html/html-tuto…...

编程日记 2025/8/24 18:38:34

大数据时代的隐私保护：区块链技术的创新应用

一、引言在当今数字化时代，大数据已经成为推动社会发展的关键力量。从商业决策到社会治理，从医疗健康到金融服务，数据的价值日益凸显。然而，随着数据的大量收集和广泛使用，隐私保护问题也日益突出。如何在充分利用大…...

编程日记 2025/8/25 16:05:42

力扣刷题-热题100题-第31题（c++、python）

25. K 个一组翻转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-nodes-in-k-group/?envTypestudy-plan-v2&envIdtop-100-liked 常规模拟根据翻转的长度找到头和尾，进入函数进行翻转主程序里有循环不断找到头和尾并拼…...

编程日记 2025/8/28 9:11:47

（四）数据检索与增强生成——让对话系统更智能、更高效

上一篇：（三）链式工作流构建——打造智能对话的强大引擎在前三个阶段，我们已经搭建了一个基础的智能对话，并深入探讨了输入输出处理和链式工作流构建的细节。今天，我们将进入智能对话系统的高级阶段——数…...

编程日记 2025/8/23 18:27:30

Turtle图形化编程知识点汇总：让编程更有趣

友情提示：本文内容由银河易创AI（https://ai.eaigx.com）创作平台gpt-4-turbo模型生成，仅供参考! 在学习编程的过程中，许多初学者会接触到Python的turtle图形库，它是一种图形化编程工具，通过简单的…...

编程日记 2025/8/22 5:12:30

Social GAN（CVPR2018)

文章目录 AbstractIntroductionRelated WorkHuman-Human InteractionRNNs for Sequence PredictionGenerative Modeling MethodProblem DeﬁnitionGenerative Adversarial NetworksSocially-Aware GANPooling ModuleEncouraging Diverse Sample Generation Conclusion paper Ab…...

编程日记 2025/8/26 18:50:32

本文涉及知识点

P6216 回文匹配

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

马拉车算法 扩展KMP 2次差分数组

单元测试

单元测试

扩展阅读

视频课程

测试环境

相关文章：

马拉车算法扩展KMP 2次差分数组