C++实现寻找最长连续重复子串

#include
#include
using namespace std;
/*
问题描述：给定一个字符串，如“ababc”，目标是找出其中最长的连续重复子串。本示例中，答案应为“ab”，因为它连续重复出现且长度最长。
下面通过C++语言编写一个函数来解决这个问题，并对算法的复杂度进行简要分析。
*/
struct SubStringInfo
{
int maxLength; // 存储最长重复子串的长度
string longestSubStr; // 存储最长重复子串
} subStrInfo;
bool isContinuous(string &mainStr, string subStr) // 判断子串是否在主串中连续重复出现
{
if (mainStr.length() == subStr.length()) return false;
size_t pos = mainStr.find(subStr); // 查找子串首次出现的位置
if (pos == string::npos) return false; // 如果未找到，则返回false
size_t nextPos = mainStr.find(subStr, pos + subStr.length()); // 查找下一个匹配位置
if (nextPos == pos + subStr.length()) return true; // 如果下一个位置正确，则说明连续重复
return false;
}
void findLongestContinuousSubStr(SubStringInfo &info, string &inputStr)
{
int strLen = inputStr.length();
for (int len = 1; len <= strLen / 2; ++len) // 遍历所有可能的子串长度（不超过总长度的一半）
{
for (int start = 0; start <= strLen - len; ++start) // 遍历所有起始位置
{
string subStr = inputStr.substr(start, len); // 获取当前子串
if (isContinuous(inputStr, subStr)) // 检查是否连续重复出现
{
if (len > info.maxLength) // 更新最长子串信息
{
info.maxLength = len;
info.lOngestSubStr= subStr;
}
}
}
}
}
int main()
{
subStrInfo.maxLength = 0; // 初始化结构体成员
subStrInfo.lOngestSubStr= "";
string inputStr;
cout <<"请输入一个字符串: ";
cin >> inputStr;
findLongestContinuousSubStr(subStrInfo, inputStr);
cout <<"最长的连续重复子串为: " < return 0;
}