【Luogu P3426】[POI2005]SZA-Template
2021/11/20 6:11:33
本文主要是介绍【Luogu P3426】[POI2005]SZA-Template,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
链接:
洛谷
题目大意:
给定一个字符串 \(s\),找到最小的 \(t\) 使得 \(t\) 匹配的位置能覆盖 \(s\)。
思路:
\(t\) 一定是 \(s\) 的一个前后缀(\(s\) 也算),考虑 DP。设 \(f_i\) 表示前缀 \(i\) 的答案,那么 \(f_i\) 要么是 \(i\),要么是 \(f_{\mathrm{border}(i)}\)。那么如果是 \(f_{\mathrm{border}(i)}\),那么某个 \(f_j=f_{\mathrm{border}(i)}\) 一定在 \([i-\mathrm{border}(i),i]\) 内。
代码:
const int N = 5e5 + 10; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * f; } char s[N]; int nxt[N], f[N], g[N];; int main() { // freopen(".in", "r", stdin); // freopen(".out", "w", stdout); scanf ("%s", s + 1); int n = strlen (s + 1); for (int i = 2, j = 0; i <= n; i++) { while (j && s[i] != s[j + 1]) j = nxt[j]; if (s[i] == s[j + 1]) j++; nxt[i] = j; } for (int i = 1; i <= n; i++) { f[i] = i; if (g[f[nxt[i]]] >= i - nxt[i]) f[i] = f[nxt[i]]; g[f[i]] = i; } printf ("%d\n", f[n]); return 0; }
这篇关于【Luogu P3426】[POI2005]SZA-Template的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行