检查字符串两端是否存在可逆相等子串

---

在这个问题中，我们需要找到从字符串开头和结尾开始的最大长度的可逆相等子串。

这个问题非常类似于寻找回文串。我们可以开始遍历字符串，直到开头和结尾的字符匹配。

问题陈述 - 我们给定一个包含 N 个字符的字符串 str。我们需要检查该字符串是否在开头和结尾包含可逆相等子串。如果我们根据给定条件找到子串，则打印最长的子串。否则，在输出中打印“false”。

示例

输入

str = "tutorialsotut"

输出

‘tut’

解释 - “tut” 出现在开头，而 “tut” 的反转出现在结尾。

输入

 str = ‘abcytrfghgyuyjcba’

输出

‘abc’

解释 - 在给定的字符串中，“abc” 出现在开头，“cab” 出现在结尾。

输入

 str = ‘vdfdvcf’

输出

False

解释 - 该字符串不包含任何可逆子串。所以，它打印 false。

方法一

在这种方法中，我们将从开头开始遍历字符串。我们将匹配字符串的开头和结尾的字符。当我们找到不匹配的字符时，我们将停止迭代。

算法

步骤 1 - 将变量 'p' 初始化为 0，将变量 'q' 初始化为字符串长度 - 1。

步骤 2 - 还将变量 'res' 初始化为一个空字符串，用于存储所需的字符串。

步骤 3 - 使用循环进行迭代，直到 'q' 大于或等于 0。

步骤 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;
// Check if the string has reversible equal substring at the start and end of a given string
void ReversibleEqual(string s) {
    // Initialize the length and pointer variables
    int len = s.size();
    int p = 0;
    int q = len - 1;
    string res = "";
    // Iterate over the string
    while (q >= 0) {
        // If characters at index p and q are the same
        if (s[p] == s[q]) {
            // append a character to 'res', and modify p and q value
            res += s[p];
            p++;
            q--;
        } else {
            break;
        }
    }
    // If the substring is not present, print 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' 字符串来优化上述解决方案。该解决方案方法与检查字符串是否为回文非常相似。