【luogu P3426】SZA-Template(字符串)(KMP)
字符串 Luogu Template KMP
2023-09-27 14:28:30 时间
SZA-Template
题目链接:luogu P3426
题目大意
给你一个字符串,然后你可以选一个字符串来生成它。
每次你可以放一个你选的字符串到当前字符串上,然后如果后面一段跟前面一段相同,那你可以重叠上去。
(就是一个位置的字符可以被多次出现,但是不能出现不同的字符)
然后你能用的最短的字符串是多短。
思路
首先一个显然的事情是满足的字符串至少是字符串的 Border。
那考虑怎样一个 Border 才可以,那就是 fail 树上到
n
n
n 的路径上相邻点都要能凑出来。
至于怎么看能不能凑出来,那就是当前一个字符串它到下一个字符串,它起码要大于等于新多的长度(就是可以两个接一起得到新的),至于为什么这个就是 Border 定义,想想就知道。
那怎么看呢,我们考虑 dfs,每次到 Border 点就把别的兄弟删去,然后链表维护中间的距离,然后每次去儿子之前把自己删掉并且更新间隙大小,那就是要间隙大小小于等于你要看的点的长度。
代码
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N = 5e5 + 100;
char s[N];
int n, l[N], r[N], fail[N], ans, gap;
bool sp[N];
vector <int> G[N];
void del(int now) {
r[l[now]] = r[now];
l[r[now]] = l[now];
}
void dfs(int now) {
if (sp[now] && now >= gap) {
ans = min(ans, now);
}
for (int i = 0; i < G[now].size(); i++) { int x = G[now][i];
if (sp[x]) continue;
dfs(x);
}
if (l[now] && r[now] != n + 1) {
gap = max(gap, r[now] - l[now]);
}
del(now);
for (int i = 0; i < G[now].size(); i++) { int x = G[now][i];
if (!sp[x]) continue;
dfs(x);
}
}
int main() {
scanf("%s", s + 1); n = strlen(s + 1);
ans = n;
G[0].push_back(1);
for (int i = 2, j = 0; i <= n; i++) {
while (j && s[i] != s[j + 1]) j = fail[j];
if (s[i] == s[j + 1]) j++; fail[i] = j; G[j].push_back(i);
}
int now = n; while (now) sp[now] = 1, now = fail[now];
for (int i = 1; i <= n; i++) l[i] = i - 1, r[i] = i + 1;
gap = 1;
dfs(0);
printf("%d", ans);
return 0;
}
相关文章
- 数据库事务,游标,触发器,存储过程,索引,数字,日期转换为字符,字符串操作,查询,分类,内连接,外连接,全连接,模糊查询,范围查询,5种聚合函数,分组查询,主键,外键,标识列
- sql server去空格函数LTRIM()RTRIM(),判断是否为空函数isnull(),以及获取字符串长度len()的使用方法
- js对url和字符串,解码,编码,解密,加密
- 【学习笔记25】JavaScript字符串的基本认识
- 判断一个字符串中出现次数最多的字符,统计这个次数
- [转]MySQL怎么将字符串转为datetime类型
- C#获取本机IP地址字符串
- 输入一个字符串,打印出该字符串中字符的所有排列-python
- 《Python Cookbook(第2版)中文版》——1.17 替换字符串中的子串—Python 2.4
- Java经典实例:处理单个字符串
- Python字符串
- 纪念逝去的岁月——C/C++字符串旋转
- 字符串 映射相应的 函数 字符串驱动技术—— MethodAddress , MethodName , ObjectInvoke
- 【JAVA】字符串练习1
- C# 代码 Unicode码和字符串相互转换
- 【Unity/C#】DateTime时间字符串,月份用英文显示