标题:重复模式 作为神的好朋友,技术男肖嘉在姜神生日时送给他一个超长字符串S。肖嘉要姜神在其中找出一个最长的字符串T,使得T在S中至少出现了两次,想说的秘密就藏在 由于字符串实在是太长了,姜神总是找不到合适的T。于是姜神请你帮他找到这个T的长度。 【输入格式】:行。一个字符串,即题目中说的S。 【输出格式】:行。一个整数,表示最长的T的长度。 【样例输入】:ababa 【样例输出】:3 「数据范围」 对于30%的数据,s长度<=100对于60%的数据,s长度<=8000对于100%的数据,s长度<=500000资源约定: 峰值内存消耗<256M CPU消耗<1000ms。写一个C语言代码。要求如上
时间: 2024-03-25 17:37:40 浏览: 52
找出一个字符串中出现次数最多的子字符串,并返回重复次数
4星 · 用户满意度95%
以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <string.h>
int main() {
char s[500005];
scanf("%s", s);
int len = strlen(s), ans = 0;
for (int i = 1; i < len - 1; ++i) {
int l = i, r = len - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (strstr(s, s + l) == strstr(s + mid, s + l)) {
l = mid;
} else {
r = mid - 1;
}
}
if (l - i + 1 > ans) {
ans = l - i + 1;
}
}
printf("%d\n", ans);
return 0;
}
```
算法思路:
对于字符串 S,我们枚举 T 的起始位置 i(下标从 0 开始),然后在 S 的后半段中寻找第二个 T。具体地,我们使用二分法,在后半段中查找一个与前半段相等的子串。
如果找到了这样的子串,说明 T 至少出现了两次,更新答案;否则,继续枚举 i。
时间复杂度:$O(n \log n)$
空间复杂度:$O(n)$
阅读全文