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

10.3考试t3(similarity)solution

题目描述

给你一个小写字母组成的字符串,求出一个这样一个最长子串,满足:

  1. 其在原串的不同位置出现了两次(起始位置不同,可以部分重叠)
  2. 其反串在原串中出现了一次(与前面两次无关)

数据范围

字符串长度 \(n \le 5e4\)

方法

考虑前缀哈希 + 二分。

如果说假设满足要求的子串为 \(s\) ,若存在 \(s\) 的长度等于 \(n\) ,那一定存在长度小于 \(s\) 的子串满足要求(比如 \(s\) 的子串),所以不难看出本题答案是具有单调性的

现在我们可以二分答案,只需考虑 check() 的写法。

因为我们二分了满足条件的字串的长度(假设为\(l\)),我们考虑开个桶,统计每个字符串出现的个数。再在反串中验证每个长度为 \(l\) 的串在正串中出现的次数是否有大于等于 \(2\) 的。

具体的实现有很多种,可以开一个 map <string, int>, 或者前缀哈希加桶。我选择了最垃圾的方法是 map <int, int> 加上一个类似st表的哈希,用倍增将子串的哈希值拼起来。

时间复杂的: \(O (n log^k n)\) ,由于方法不同 \(k\) 可能在 1~3 中任意的数,但对于 \(5e4\) 的数据是绝对能过得。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define usd unsigned
#define el cout << '\n'
#define lowbit(x) (x & (-x))
const int ranmod = 1e7;
#define random ((rand() * rand()) % ranmod)
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
// void init();
void main_();
signed main() {ios :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);// freopen("similarity.in", "r", stdin);// freopen("similarity.out", "w", stdout);int t = 1;// cin >> t;while(t--) {// init();main_();}AK;
}
const int mod = 95225987, maxn = 5 * 1e5 + 18;
const usd int p = 2591;string s, s1;
int n; 
usd int hsh[maxn][16], hsh1[maxn][16], nxt[maxn][16];
map <usd int, long> cnt;usd int ksm(usd int a, usd int b) {usd int res = 1;do {if(b & 1) res *= a;a *= a, b = b >> 1;} while(b);return res;
}bool check(int num) {// debug(num);cnt.clear();for(int i = 1; i <= n; i++) {if(i + num - 1 > n) break;usd int fl = i, hs = 0;for(int k = 15; k >= 0; k--) {if(fl + (1ll << k) <= i + num) {hs = hs * ksm(p, (1ll << k)) + hsh[fl][k];fl += (1ll << k);}}// debug(hs);cnt[hs]++;}for(int i = 1; i <= n; i++) {if(i + num - 1 > n) break;usd int fl = i, hs = 0;for(int k = 15; k >= 0; k--) {if(fl + (1ll << k) <= i + num) {hs = hs * ksm(p, (1ll << k)) + hsh1[fl][k];fl += (1ll << k);}}if(cnt[hs] >= 2) {// debug(num), debug(i);// debug(hs), debug(cnt[hs]);return true;}}return false;
}void main_() {cin >> s;n = s.length();for(int i = n - 1; i >= 0; i--) s1 += s[i];s = ' ' + s;s1 = ' ' + s1;for(int i = 1; i <= n; i++) hsh[i][0] = s[i], hsh1[i][0] = s1[i];for(int k = 1; k <= 15; k++) {for(int i = 1; i <= n; i++) {if(i + (1ll << (k - 1)) - 1 > n) continue;hsh[i][k] = hsh[i][k - 1] * ksm(p, 1ll << (k - 1)) + hsh[i + (1ll << (k - 1))][k - 1];hsh1[i][k] = hsh1[i][k - 1] * ksm(p, 1ll << (k - 1)) + hsh1[i + (1ll << (k - 1))][k - 1];}}int l = 2, r = n, ans = 1;while(l <= r) {int mid = l + (r - l) / 2;if(check(mid)) {ans = mid;l = mid + 1;}else r = mid - 1;}cout << ans; el;
}
http://www.hskmm.com/?act=detail&tid=23789

相关文章:

  • 安卓渗透测试流
  • 日志|寻找旋转排序数组中的最小值|寻找两个正序数组的中位数|二分查找
  • 有关三角剖分的性质
  • 西门子通信-自制示意
  • Vue之刷新页面会触发的生命周期函数
  • 傅里叶的一生
  • Dos命令学习(新手)
  • 吴恩达深度学习课程一:神经网络和深度学习 第一周:深度学习简介
  • 实用指南:AI Agent开发平台如何设计?核心架构与工作流实战案例详解
  • Numercial result of HAA-DRSM
  • 防重复提交的实现
  • Day25错误(error)与异常(exception)的简单认识
  • 算法课第一次作业
  • 1. 对拍板子
  • Luogu P14122 [SCCPC 2021] Direction Setting题解 最小费用流
  • MySQL_基础
  • 5 qoj14553 序列与整数对 题解
  • AT_arc064_d [ARC064F] Rotated Palindromes
  • vscode代码块格式转换器
  • 二分模板
  • 如何控制事务?
  • C语言速成秘籍——跳转语句(goto) - 实践
  • 五子棋-下满了格子平局
  • 从免疫原性突破到技术迭代:全人源抗体如何重塑靶向治疗格局?
  • 工作感受月记(202510月)
  • 欧几里得算法与扩展欧几里得算法详解
  • 题解:AT_agc038_f [AGC038F] Two Permutations
  • 10.3 考试总结
  • CSP-S 复赛指南(2025年版)
  • AI元人文系列文章:AI元人文的未来——软硬件协同