枚举所有可能的重合长度，分别检查两个方向的“后缀等于前缀”，取最大合法长度。
OJ: luogu
题目 ID: P2957
难度:入门
标签:字符串枚举
日期: 2026-06-19 10:28
题意
给出两个字符串。
要求找出最长的重复部分长度。这里的重复部分指的是：
- 是一个字符串的前缀；
- 同时是另一个字符串的后缀。
两个方向都要考虑。
思路
因为字符串长度最大只有 80，直接枚举长度最简单。
最直接的教学版写法如下：
cpp
// brute.cpp：直接枚举重合长度并逐字符比较，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;
string s, t;
bool same_suffix_prefix(const string &a, const string &b, int len) {
int n = (int) a.size();
for (int i = 0; i < len; i++) {
if (a[n - len + i] != b[i]) {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> t;
int ans = 0;
int limit = min((int) s.size(), (int) t.size());
for (int len = 1; len <= limit; len++) {
if (same_suffix_prefix(s, t, len)) {
ans = max(ans, len);
}
if (same_suffix_prefix(t, s, len)) {
ans = max(ans, len);
}
}
cout << ans << '\n';
return 0;
}我们枚举一个长度 len，然后检查两件事：
s的后len位是否等于t的前len位；t的后len位是否等于s的前len位。
只要某个方向成立，就可以用这个 len 更新答案。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
string s, t;
bool same_suffix_prefix(const string &a, const string &b, int len) {
int n = (int) a.size();
for (int i = 0; i < len; i++) {
if (a[n - len + i] != b[i]) {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> t;
int ans = 0;
int limit = min((int) s.size(), (int) t.size());
for (int len = 1; len <= limit; len++) {
if (same_suffix_prefix(s, t, len)) {
ans = max(ans, len);
}
if (same_suffix_prefix(t, s, len)) {
ans = max(ans, len);
}
}
cout << ans << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
这里 n 是字符串长度上限，最多只有 80。
总结
这题不需要复杂字符串算法。
数据很小，直接枚举重合长度并比较前后缀，就是最稳的做法。