Periods of Words
2022/4/26 6:13:03
本文主要是介绍Periods of Words,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
对于一个仅含小写字母的字符串 a,p 为 a 的前缀且 p≠a,那么我们称 p 为 a 的 proper 前缀。
规定字符串 Q(可以是空串)表示 a 的周期,当且仅当 Q 是 a 的 proper 前缀且 a 是 Q+Q 的前缀。
例如 ab
是 abab
的一个周期,因为 ab
是 abab
的 proper 前缀,且 abab
是 ab+ab
的前缀。
求给定字符串所有前缀的最大周期长度之和。
输入格式
In the first line of the standard input there is one integer kk (1\le k\le 1\ 000\ 0001≤k≤1 000 000) - the length of the string. In the following line a sequence of exactly kk lower-case letters of the English alphabet is written - the string.
输出格式
In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.
输入输出样例
输入 #18 babababa输出 #1
24
分析:
找出所给字符串所有前缀子串的最长周期的长度之和。
以babababa为例,每个前缀字串的最长周期分别为:
b 0
ba 0
bab ba 【b】
baba ba 【ba】
babab baba 【b】
bababa baba 【ba】
bababab bababa 【b】
babababa bababa 【ba】
所以只需求出它的最短相同前后缀的长度,再用这个子串的长度减去这个最短相同前后缀的长度。
代码
#include <iostream> using namespace std; int main() { int len,n = 0,b[1000005]; //字符串长度len,相同前后缀长度n,记录前缀子串最长周期的数组b scanf("%d",&len); char a[1000005]; //存放字符串的数组a scanf("%s",a); b[0]=0; b[1]=0; //前两个前缀子串的周期都为0 for (int i = 1;i < len;i++) { while (n>0 && a[i]!=a[n]) { n = b[n]; } if (a[i] == a[n]) n++; b[i+1] = n; } long long ans = 0; //最长周期之和ans for (int i = 1;i <= len;i++) { n = i; while (b[n]!=0) n = b[n]; if (b[i]!=0) b[i] = n; ans = ans + i - n; //子串长度-相同前后缀长度 } cout << ans; //或printf("%lld",ans); return 0; }
这篇关于Periods of Words的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 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?