用C++:给定两个字符串X和Y,编写算法寻找字符串X的最长前缀同时是字符串Y的后缀。
时间: 2024-09-27 09:08:45 浏览: 54
要解决这个问题,你可以使用 C++ 的标准库来编写一个函数,这个函数可以找到字符串 X 的最长前缀,它同时也是字符串 Y 的后缀。以下是一个简单的解决方案:
```cpp
#include <iostream>
#include <string>
bool isSuffixOf(const std::string& mainStr, const std::string& subStr) {
// 如果子串比主串长,则不可能是后缀
if (subStr.size() > mainStr.size()) {
return false;
}
// 使用 rfind 查找子串在主串中的最后一个匹配位置
size_t pos = mainStr.rfind(subStr);
// 如果找到子串并且其位置等于子串长度,说明它是后缀
return pos != std::string::npos && pos == mainStr.size() - subStr.size();
}
std::string longestCommonPrefixAndSuffix(const std::string& x, const std::string& y) {
// 判断 Y 是否是 X 的后缀
if (!isSuffixOf(x, y)) {
return "";
}
// 从 X 的末尾开始向前查找最长公共前缀,直到找到不是 Y 的部分
for (size_t i = x.size(); i >= y.size(); --i) {
if (x.substr(i, y.size()) != y) {
return x.substr(0, i);
}
}
return x; // 如果整个 X 都是 Y 的后缀,直接返回 X
}
int main() {
std::string x = "banana";
std::string y = "anan";
std::cout << "Longest common prefix and suffix of X that is also a suffix of Y: " << longestCommonPrefixAndSuffix(x, y) << std::endl;
return 0;
}
```
这段代码首先定义了一个 `isSuffixOf` 函数检查字符串 Y 是否是字符串 X 的后缀。然后,`longestCommonPrefixAndSuffix` 函数从 X 的末尾开始查找最长的公共前缀,只要这个前缀仍然是 Y 的后缀,就继续向前查找。当找不到这样的前缀时,返回到目前为止找到的部分作为结果。
阅读全文