檢查字串兩端是否存在可逆相等子串

---

在這個問題中，我們需要找到從字串開頭和結尾開始的最大長度的可逆相等子串。

這個問題非常類似於尋找回文串。我們可以開始遍歷字串，直到開頭和結尾的字元匹配。

問題陳述 - 我們給定一個包含 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' 字串來最佳化上述解決方案。該解決方案方法與檢查字串是否為迴文非常相似。