密码截获-题解（C++代码）穷举 + 优化，马拉车还没消化，以后补上

———————————————————————————————    M 1    ————————————————————————————————

解题思路:
        穷举str的所有子串，调用回文串判断函数bool isPalindromeStr(string s)

注意事项:
        设n为字符串长度，判断一个回文串 O(n)，遍历所有字串 O(n²)，总时间复杂度 O(n³) ，空间复杂度 O(n)  用来存字符串
参考代码:

#include<bits/stdc++.h>
using namespace std;
bool isPalindromeStr(string s)
{
    int len = s.length();
    int len_half = len / 2;
    for (int i = 0; i < len_half; ++i) {
        if (s[i] != s[len - 1 - i]) return false;
    }
    return true;
}

int main()
{
    string s;
    while (cin >> s) {
        int i, j;
        int sLen = s.length();
        int maxLen = 0;
        // 核心：两层循环，依次检索 substr(i, j) 即 s[i] 开始，长度为 j 的子串
        for (i = 0; i < sLen; ++i) {
            for (j = sLen - i; j >= 1; --j) {
                if (isPalindromeStr(s.substr(i, j)) && j > maxLen) {
                    maxLen = j;
                }
            }
        }
        cout << maxLen << endl;
    }

    return 0;
}

———————————————————————————————    M 2    ————————————————————————————————

解题思路:
        以字符或空隙作为中心，扩展子串，判断str的部分子串

        优化原理：若 abc 不为回文串，则 xabcx 也不会是回文串，再向外延伸也不满足，以此减少判断的子串数量

        优化后，设n为字符串长度，判断一个回文串 O(n)，遍历所有字串 O(n)，总时间复杂度 O(n²) ，空间复杂度 O(n)  用来存字符串

        （这一步遍历所有字串 O(n)说实话我还没完全理解，但是应该接近这个数量级

注意事项:
        代码比较繁杂，重复度高，有兴趣的可以看看.....不打算优化结构了，还要学马拉车算法......

        举个例子：str = "abc"

        以字符为中心扩展：a / b, abc / c

        以空隙为中心扩展：ab / bc

        难以理解的话，用#代替空隙：str = "a#b#c" 【实际上，这样填充得到的字符串，与原字符串的回文特性等价】

        代码中多处break避免了无意义的判断，使得寻找最长回文字串变成了一个有大致方向的寻找。希望这样的表述还算可以......

        如：str = "adaelele"  穷举有36个字串  优化后：以标红的e为中心扩展：e ——> lel ——> elele

参考代码:

#include<bits/stdc++.h>
using namespace std;

bool isPalindromeStr(string s)
{
    int len = s.length();
    int len_half = len / 2;
    for (int i = 0; i < len_half; ++i) {
        if (s[i] != s[len - 1 - i]) return false;
    }
    return true;
}

int main()
{
    string s;
    while (cin >> s) {
        int i, j, k;
        int sLen = s.length();
        int maxSLen = 0;
        string maxS;
        // 前半部分 s[0]~s[len/2 - 1]
        for (i = 0; i < sLen / 2; ++i) {
            // 判断字符
            for (j = 1, k = i; k >= 0; j += 2, --k) {
                if (isPalindromeStr(s.substr(k, j))) {
                    if (j > maxSLen) {
                        maxS = s.substr(k, j);
                        maxSLen = j;
                    }
                }
                else break;
            }
            // 判断空隙
            for (j = 2, k = i; k >= 0; j += 2, --k) {
                if (isPalindromeStr(s.substr(k, j))) {
                    if (j > maxSLen) {
                        maxS = s.substr(k, j);
                        maxSLen = j;
                    }
                }
                else break;
            }
        }
        // 后半部分 s[len/2]~s[len-1]
        for (i = sLen / 2; i < sLen; ++i) {
            // 判断字符
            for (j = 1, k = i; j + k <= sLen; j += 2, --k) {
                if (isPalindromeStr(s.substr(k, j))) {
                    if (j > maxSLen) {
                        maxS = s.substr(k, j);
                        maxSLen = j;
                    }
                }
                else break;
            }
            // 判断空隙
            for (j = 2, k = i; j + k <= sLen; j += 2, --k) {
                if (isPalindromeStr(s.substr(k, j))) {
                    if (j > maxSLen) {
                        maxS = s.substr(k, j);
                        maxSLen = j;
                    }
                }
                else break;
            }
        }
        cout << maxSLen << endl;
    }
    return 0;
}

———————————————————————————————    M 3    ————————————————————————————————

马拉车算法迟点补......