A40883. 重复模式
填空题
困难
知识点
题目描述
重复模式
题目描述
作为 drd 的好朋友，技术男 atm 在 drd 生日时送给他一个超长字符串 S 。
atm 要 drd 在其中找出一个最长的字符串 T ，使得 T 在 S 中至少出现了两次，而他想说的秘密就藏在 T 中。
由于字符串实在是太长了，drd 总是找不到合适的 T ，于是 drd 请你帮他找到这个 T 的长度。
输入格式
一行。一个字符串，即题目中说的 S 。
输出格式
一个整数，表示最长的 T 的长度。
样例输入
ababa
样例输出
3
数据范围
对于 30% 的数据，S 长度 ≤ 100
对于 60% 的数据，S 长度 ≤ 8000
对于 100% 的数据，S 长度 ≤ 500000
参考答案
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < s.size() - 1; i ++)
for (int len = 1; len < s.size(); len ++)
{
if(i + len > s.size()) break;
if(s.find(s.substr(i, len), i + 1) != -1)
ans = max(ans, len);
}
cout << ans << endl;
return 0;
}答案解析
s.substr(pos, len)：从字符串 s 的下标 pos 开始，截取一段长度为 len 的字符串。s.find(str, pos)：从字符串 s 的下标 pos 开始，匹配 str，成功返回其在 s 中第一次出现的位置，失败返回 -1
上一题
下一题