检查字符串两端是否有可逆相等子字符串
data structurec++server side programming
在这个问题中，我们需要从字符串的开头和结尾找到最大长度的可逆相等子字符串。
这个问题与查找回文字符串非常相似。我们可以开始遍历字符串，然后遍历字符串，直到开头和结尾的字符匹配为止。
问题描述− 我们给出了包含 N 个字符的字符串 str。我们需要检查字符串是否在字符串的开头和结尾包含可逆相等子字符串。如果我们根据给定的条件找到子字符串，则打印最长的子字符串。否则，在输出中打印"false"。
示例
输入
str = "tutorialsotut"
输出
'tut'
解释 − 'tut' 出现在开头，'tut' 的反面出现在结尾。
输入
str = 'abcytrfghgyuyjcba'
输出
'abc'
解释 − 在给定的字符串中，'abc' 位于开头，'cab' 位于结尾。
输入
str = 'vdfdvcf'
输出
False
解释 − 字符串不包含任何可逆子字符串。因此，它打印 false。
方法 1
在此方法中，我们将从开头开始遍历字符串。我们将从开头和结尾匹配字符串的字符。当我们发现不匹配的字符时，我们将停止迭代。
算法
步骤 1 - 用 0 初始化"p"变量，用字符串长度 - 1 初始化"q"变量。
步骤 2 - 另外，用空字符串初始化"res"变量以存储所需的字符串。
步骤 3 - 使用循环进行迭代，直到"q"大于或等于零。
步骤 4 - 如果 s[p] 和 s[q] 字符相等，则将它们附加到"res"字符串。另外，将 p 值增加 1，将 q 减少 1。
步骤 5 − 如果 s[p] 和 s[q] 不相同，则使用"break"关键字中断循环。
步骤 6 − 如果"res"字符串的大小等于零，则打印 false。否则，打印"res"字符串。
示例
#include <bits/stdc++.h>
using namespace std;
// 检查字符串在给定字符串的开头和结尾是否具有可逆相等子字符串
void ReversibleEqual(string s) {
// 初始化长度和指针变量
int len = s.size();
int p = 0;
int q = len - 1;
string res = "";
// 遍历字符串
while (q >= 0) {
// 如果索引 p 和 q 处的字符相同
if (s[p] == s[q]) {
// append a character to 'res', and modify p and q value
res += s[p];
p++;
q--;
} else {
break;
}
}
// 如果子字符串不存在，则打印 False
if (res.size() == 0)
cout << "False";
// print true
else {
cout << "True \n"
<< res;
}
}
int main() {
string str = "tutorialsotut";
ReversibleEqual(str);
return 0;
}
输出
True tuto
时间复杂度− O(N)，因为我们使用循环来迭代字符串
空间复杂度− O(N)，因为我们存储可逆字符串。
程序员可以通过直接打印每个字符而不是将其附加到"res"字符串来优化上述解决方案。解决方法与检查字符串是否为回文非常相似。
