5.最長回文子串

[TOC]

一、題目描述

給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案赵辕。

示例 2：

輸入: "cbbd"
輸出: "bb"

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)概龄，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處还惠。

二、解題算法

1. 暴力法

思路：

我不是針對(duì)誰私杜，顯然在座的各位都會(huì)判別一個(gè)給定的字符串是不是回文串蚕键，那我只要枚舉 s 的全部子串救欧，然后逐個(gè)判斷是不是回文串不就好了嗎？題意要求最長的回文子串锣光，我還可以按子串長度從長到短去枚舉笆怠，提升效率，美滋滋疤艿蹬刷！

但粗略估計(jì)一下，需要枚舉長度频丘、左端點(diǎn)箍铭，然后再遍歷子串，時(shí)間復(fù)雜度需要到 $O(n^3)$ 椎镣，性能好像不是很耐看？（我沒有莽過兽赁，也許可以過状答，哪位大佬有興趣可以試試？）

2. 動(dòng)態(tài)規(guī)劃

2.1 常規(guī)操作

思路：

既然暴力法不是很劃算刀崖，我們就得進(jìn)一步思考一下如何進(jìn)行優(yōu)化惊科。
暴力法主要的問題在于冗余計(jì)算。若 $s[i] \sim s[j]$ 不是回文串亮钦，那 $s[i-1] \sim s[j+1]$ 肯定不是回文串馆截，而暴力法無法有效地利用這個(gè)信息。

嗯蜂莉，雖然上面只是舉了一個(gè)例子蜡娶，但這個(gè)例子好像透露出一股優(yōu)化方案的味道？因?yàn)檎者@種方法映穗，對(duì)任意子串窖张，我們可以在 $O(1)$ 的時(shí)間內(nèi)來判別其是否為回文串，而不像暴力法中需要用 $O(n)$ 的時(shí)間來判斷蚁滋。
記 $dp[i][j]$ 為子串 $s[i] \sim s[j]$ 的回文長度（非回文串長度為0宿接，回文串為子串長度），我們顯然可以得到下述狀態(tài)轉(zhuǎn)移方程：
$\begin{equation} dp[i][j]= \begin{cases} 0辕录，& s[i] \ne s[j]\ \text{or}\ dp[i+1][j-1] = 0\\ dp[i+1][j-1]+2,& s[i] = s[j]\ \text{and}\ dp[i+1][j-1] \ne 0 \end{cases} \end{equation}$
有了狀態(tài)轉(zhuǎn)移方程睦霎，下面就是如何初始化這個(gè) $dp$ 數(shù)組的問題了。
我們可以注意到走诞，這種思路其實(shí)是從某個(gè)中心子串出發(fā)副女，向兩邊擴(kuò)張的過程。所以我們只要初始化最根本的中心蚣旱，剩下的都可以靠擴(kuò)張過程得到肮塞。
那么顯然襟齿，所有長度為1的子串都是中心。同時(shí)我們需要注意到枕赵，如果將長度為1的子串作為中心猜欺，由于每次擴(kuò)張都會(huì)納入2個(gè)新的字符，所以它只能擴(kuò)張為奇數(shù)長度的子串拷窜。為了保證同時(shí)考慮到偶數(shù)長度的子串开皿，我們必須將所有長度為2的子串也作為中心。于是有了如下初始化方程：
$dp[i][i] = 1 \\ \begin{equation} dp[i][i+1]= \begin{cases} 0, & s[i] \ne s[i+1] \\ 2, & s[i] = s[i+1] \end{cases} \end{equation}$
時(shí)間復(fù)雜度 $O(n^2)$ 篮昧，空間復(fù)雜度 $O(n^2)$ 赋荆。

代碼：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty())
            return "";

        vector<vector<int>> dp(s.length(), vector<int>(s.length()));
        for (auto i = 0; i < dp.size(); ++i)
            dp[i][i] = 1;
        for (auto i = 0; i < dp.size() - 1; ++i)
            dp[i][i + 1] = (s[i] == s[i + 1]) ? 2 : 0;
        for (auto len = 3; len <= s.length(); ++len)
            for (auto i = 0; i < s.length() - len + 1; ++i)
                if (dp[i + 1][i + len - 2] > 0 &&
                    s[i] == s[i + len - 1])
                    dp[i][i + len - 1] = len;

        auto ans = 0, begin = 0, end = 0;
        for (auto i = 0; i < dp.size(); ++i)
            for (auto j = 0; j < dp[i].size(); ++j)
                if (ans < dp[i][j]) {
                    ans = dp[i][j];
                    begin = i;
                    end = j;
                }
        return s.substr(begin, end - begin + 1);
    }
};

2.2 修正一個(gè)小的缺陷

思路：

2.1的解決方案有點(diǎn)小瑕疵，觀察代碼我們發(fā)現(xiàn)在計(jì)算 $dp$ 數(shù)組的雙重循環(huán)中懊昨，先遍歷的是 $len$ 窄潭，后遍歷的 $i$ 。這樣更容易出現(xiàn)緩存不命中的情況酵颁，因而可以考慮對(duì)代碼進(jìn)行調(diào)整嫉你，讓其先遍歷 $i$ ，再遍歷 $len$ 躏惋。

圖1 計(jì)算過程示意圖

示意圖以長度為5的字符串為例幽污。○表示長度為1的子串簿姨，×表示長度為2的子串距误，以此類推。
按照2.1的邏輯扁位，我們的計(jì)算過程是每次外循環(huán)決定計(jì)算哪一條斜線（一條斜線代表一種子串長度）准潭，內(nèi)循環(huán)再去將該斜線中的節(jié)點(diǎn)從上自下算出（該長度的所有子串）。且代碼中計(jì)算需要利用到域仇，在圖中形象的來說就是計(jì)算從△起（因?yàn)椤鸶潦浅跏蓟耐锒欤瑹o需計(jì)算）的任一節(jié)點(diǎn)，都必須要用到它左下角的節(jié)點(diǎn)殉簸。
因此闰集，如果我們想整行整行的遍歷，不能從上往下般卑，因?yàn)槊總€(gè)節(jié)點(diǎn)依賴于它的左下角的節(jié)點(diǎn)武鲁，只能從下往上。

時(shí)間復(fù)雜度 $O(n^2)$ 蝠检，空間復(fù)雜度 $O(n^2)$ 沐鼠。

代碼：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty())
            return "";

        vector<vector<int>> dp(s.length(), vector<int>(s.length()));
        for (auto i = 0; i < dp.size() - 1; ++i) {
            dp[i][i] = 1;
            dp[i][i + 1] = (s[i] == s[i + 1]) ? 2 : 0;
        }
        dp.back().back() = 1;
        
        for (auto i = int(dp.size()) - 1; i > -1; --i)
            for (auto len = 3; i + len - 1 < s.length(); ++len)
                if (dp[i + 1][i + len - 2] > 0 &&
                    s[i] == s[i + len - 1])
                    dp[i][i + len - 1] = len;

        auto ans = 0, begin = 0, end = 0;
        for (auto i = 0; i < dp.size(); ++i)
            for (auto j = 0; j < dp[i].size(); ++j)
                if (ans < dp[i][j]) {
                    ans = dp[i][j];
                    begin = i;
                    end = j;
                }
        return s.substr(begin, end - begin + 1);
    }
};

然而雖然我這么處理了，但速度提升并不明顯，只是有些輕微的提升饲梭，讓我有點(diǎn)蒙圈乘盖。或許瓶頸其實(shí)并不在緩存不命中這里憔涉？

2.3 滾動(dòng)數(shù)組

思路：

行吧订框，那我放棄掙扎了，好不容易想到個(gè)方案想提速結(jié)果竟然沒啥明顯的作用兜叨，說好的學(xué)會(huì)利用緩存會(huì)有奇效的呢穿扳？都是騙人的！生氣国旷！
老老實(shí)實(shí)的優(yōu)化我那瘆人的空間復(fù)雜度吧矛物， $O(n^2)$ 導(dǎo)致在我的幾次提交之中，基本都要消耗186MB的內(nèi)存跪但，這太恐怖了履羞，必須控制一下。

按照滾動(dòng)數(shù)組常規(guī)的思考方向屡久，動(dòng)態(tài)規(guī)劃中用來保存狀態(tài)的 $dp$ 數(shù)組我們可以看到他只用了上三角部分來保存數(shù)據(jù)忆首，下三角部分完全沒有使用。且涂身，在2.2中我們描述過，對(duì)從△起的任一節(jié)點(diǎn)搓蚪，我們都只要額外知道他左下角的節(jié)點(diǎn)就可以了蛤售。這就給了我們一種思考方向，或許妒潭，我們只需要2行悴能，便可以計(jì)算出 $dp$ 數(shù)組。

另外雳灾，由于需要左下角節(jié)點(diǎn)漠酿，那我們也必須像2.2中一樣，將 $dp$ 數(shù)組從下往上倒過來計(jì)算谎亩。而且炒嘲，由于只使用2行，如何初始化 $dp$ 數(shù)組也需要注意一下匈庭。
我們知道按照2.1和2.2的初始化方法夫凸，我們必然要在處理每一行的時(shí)候初始化 $dp[cur][i]$ 和 $dp[cur][i+1]$ （想想 $dp$ 數(shù)組表示的狀態(tài)是什么），初始化方式和正常初始化一樣阱持。但由于倒數(shù)第一行只有1個(gè)節(jié)點(diǎn)夭拌，所以我們需要把這一行單獨(dú)拿出來計(jì)算。

時(shí)間復(fù)雜度 $O(n^2)$ ，空間復(fù)雜度 $O(n)$ 鸽扁。

代碼：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty())
            return "";

        auto cur = 1, prev = 0, ans = 1, begin = 0, end = 1;
        vector<vector<int>> dp(2, vector<int>(s.length(), 0));
        dp[0].back() = 1;
        for (auto i = int(s.length()) - 2; i > -1; --i) {
            dp[cur][i] = 1;
            dp[cur][i + 1] = s[i] == s[i + 1] ? 2 : 0;
            if (dp[cur][i + 1] > ans) {
                ans = dp[cur][i + 1];
                begin = i; end = i + 2;
            }
            for (auto j = i + 2; j < s.length(); ++j)
                if (dp[prev][j - 1] > 0 && s[i] == s[j]) {
                    dp[cur][j] = dp[prev][j - 1] + 2;
                    if (dp[cur][j] > ans) {
                        ans = dp[cur][j];
                        begin = i; end = j + 1;
                    }
                }
                else
                    dp[cur][j] = 0;
            prev = cur;
            cur = 1 - cur;
        }
        return s.substr(begin, end - begin);
    }
};

嗯蒜绽？我明明只是優(yōu)化了內(nèi)存，所以內(nèi)存從168MB優(yōu)化到9.5MB合情合理桶现。但為什么執(zhí)行速度也提高了躲雅？從300ms+縮減到了132ms？
天地良心巩那，除了使用的內(nèi)存減少了吏夯，算法基本上沒做任何太大改動(dòng)啊。也就是最多把求解 $begin$ 和 $end$ 的過程移動(dòng)到了循環(huán)內(nèi)即横。但這也是平方次的比較噪生，會(huì)有很大的差別嗎？難道瓶頸在于之前開辟 $dp$ 數(shù)組的時(shí)候东囚？又或者因?yàn)檫@次因?yàn)閮?nèi)存足夠小跺嗽，所以提高了緩存的執(zhí)行性能？
好迷啊页藻，估摸著回頭有時(shí)間真的得用宇宙第一IDE來調(diào)試看看瓶頸到底在哪了桨嫁，總比我這瞎猜來得強(qiáng)。

3. 中心擴(kuò)展算法

3.1 常規(guī)操作

思路：

其實(shí)思路已經(jīng)沒什么好說的了吧份帐，畢竟動(dòng)態(tài)規(guī)劃的解法里已經(jīng)把思路都說了璃吧。防止有大佬看不起我動(dòng)態(tài)規(guī)劃的解法，這里還是把思路再稍微提一下废境。
中心擴(kuò)展算法畜挨，說白了就是枚舉回文子串的中心，然后從中心往兩邊擴(kuò)展噩凹，得到以該節(jié)點(diǎn)為中心所能構(gòu)成的最長回文子串巴元。唯一要注意以下的就是回文中心分為奇數(shù)長度與偶數(shù)長度兩種，其長度分別為1和2驮宴。

設(shè)字符串長度為 $n$ 逮刨，在枚舉長度為1的中心時(shí)，這 $n$ 個(gè)都被枚舉了堵泽。而枚舉長度為2的中心時(shí)修己，一共有 $n-1$ 組中心可以被枚舉。因而總共枚舉 $2n-1$ 個(gè)中心迎罗，每次枚舉中心最壞要檢查 $n$ 個(gè)字符箩退。然而不需要額外空間記錄搜索狀態(tài)。

時(shí)間復(fù)雜度 $O(n^2)$ 佳谦，空間復(fù)雜度 $O(1)$ 戴涝。

代碼：

class Solution {
public:
    int count(string& s, int lhs, int rhs) {
        while (lhs > -1 && rhs < s.length() && s[lhs] == s[rhs]) {
            lhs--; rhs++;
        }
        return rhs - lhs - 1;
    }
    
    string longestPalindrome(string s) {
        if (s.length() < 2)
            return s;
        
        auto begin = 0, end = 0, max_len = 0;
        for (size_t i = 0; i < s.size(); ++i) {
            auto len1 = count(s, i, i);
            auto len2 = count(s, i, i + 1);
            max_len = max(len1, len2);
            if (max_len > end - begin + 1) {
                begin = i - (max_len - 1) / 2;
                end = i + max_len / 2;
            }
        }
        return s.substr(begin, end - begin + 1);
    }
};

3.2 如果你對(duì)奇偶兩種中心如鯁在喉

思路：

嗯，如果看到這的話，那你一定是真的對(duì)上面需要處理兩種中心的情況心懷不滿了啥刻，覺得不夠優(yōu)雅奸鸯。那么這里提供一個(gè)小的技巧可以將奇偶兩種情況轉(zhuǎn)變?yōu)橐环N。

鄭重聲明：該技巧使用后可帽，時(shí)間復(fù)雜度與空間復(fù)雜度的系數(shù)或者數(shù)量級(jí)均會(huì)有不同程度的上升娄涩，性能是有所下降的。這里僅僅是當(dāng)做擴(kuò)展思路映跟、開拓眼界而提及的（顯然這并不是我原創(chuàng)的）蓄拣。另外，之所以不在動(dòng)態(tài)規(guī)劃引入努隙，是因?yàn)閷?duì)動(dòng)態(tài)規(guī)劃來說球恤，再使用這個(gè)技巧，代價(jià)有點(diǎn)難以承受荸镊。

我們之所以會(huì)遇到奇偶的問題咽斧，很顯然是因?yàn)榛匚淖哟L度 $n$ 它可能是奇數(shù)，也可能是偶數(shù)躬存。如果张惹，我是說如果，我們能夠?qū)⒒匚淖哟拈L度統(tǒng)一成奇數(shù)或者偶數(shù)岭洲，那不就可以不用分情況討論了嗎宛逗？
對(duì)，比如說將 $n$ 盾剩，變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=2n%2B1" alt="2n+1" mathimg="1">雷激。那它們就顯然被統(tǒng)一成了奇（長度的）（回文）子串，就只要考慮中心為單個(gè)字符的情況了彪腔。

那現(xiàn)在問題來了侥锦，我怎么把子串長度從 $n$ 擴(kuò)展到 $2n+1$ 呢进栽？其實(shí)很簡(jiǎn)單德挣，往原串插入字符就好了，用某個(gè)特定的字符去擴(kuò)張?jiān)?br>

圖2 擴(kuò)展示意圖

注意快毛，這里選擇#作為擴(kuò)展字符并沒有什么特殊的含義格嗅，只要能保證用來擴(kuò)展的字符不存在于原串之中，你愛選啥就選啥唠帝。

我們可以看到屯掖，
對(duì)于每一個(gè)實(shí)線方框內(nèi)，擴(kuò)展串的下標(biāo) $i$ 襟衰，只要取 $\lfloor i/2 \rfloor$ 贴铜，便能得到原串中的下標(biāo)。這便于我們之后通過掃表擴(kuò)展串，來從原串中找到對(duì)應(yīng)的子串绍坝。同理徘意，擴(kuò)展子串長度若為 $len$ ，只要取 $\lfloor len/2 \rfloor$ 轩褐，便能得到原子串的長度椎咧。
對(duì)于每一個(gè)虛線方框，不管其對(duì)應(yīng)原串是偶子串還是奇子串把介，在擴(kuò)展串中都是奇子串勤讽，并且左右兩端一定是#。唯一區(qū)別是原偶子串在擴(kuò)展串中拗踢，中心為#脚牍。而原奇子串在擴(kuò)展串中，中心為（原串中）奇子串對(duì)應(yīng)的中心秒拔。之后在計(jì)算子串對(duì)應(yīng)邊界時(shí)會(huì)用到這個(gè)性質(zhì)莫矗。

好了，接著對(duì)擴(kuò)展串采用中心擴(kuò)展算法的思路砂缩，就可以得到最長的那個(gè)擴(kuò)展子串作谚。接下來只要想辦法將其還原成原子串就好了。
原子串的中心和長度上面已經(jīng)描述過計(jì)算方法了庵芭，問題就在于如何求左右兩個(gè)端點(diǎn)妹懒。
可能有同志說，有中心坐標(biāo)双吆，也有字串長度了眨唬，直接 $begin = center - \lfloor len/2 \rfloor$ ， $end = center + \lfloor len/2 \rfloor$ 不是很明顯的嗎好乐？

果真如此嗎匾竿？不要忘了，原子串是分奇偶兩種子串的蔚万，而該公式只適用于原子串為奇子串的情況岭妖。因?yàn)楦鶕?jù) $len$ 的奇偶， $end - begin$ 并不是一個(gè)定值反璃。因此這里采用了 $begin = center - \lfloor len / 2 \rfloor$ 昵慌， $end = center + len - \lfloor len / 2 \rfloor$ 。這樣淮蜈，無論 $len$ 的奇偶如何斋攀， $end - begin \equiv len$ 。

時(shí)間復(fù)雜度 $O(n^2)$ 梧田，空間復(fù)雜度 $O(n)$ 丧失。

代碼：

class Solution {
public:
    int count(vector<char>& s, int lhs, int rhs) {
        while (lhs > -1 && rhs < s.size() && s[lhs] == s[rhs]) {
            lhs--; rhs++;
        }
        return rhs - lhs - 1;
    }
    
    string longestPalindrome(string s) {
        if (s.size() < 2)
            return s;

        vector<char> str(2 * s.size() + 1, '#');
        for (auto i = 0; i < s.size(); ++i)
            str[i * 2 + 1] = s[i];
        
        auto begin = 0, end = 0, max_len = 0;
        for (auto i = 0; i < str.size(); ++i) {
            auto len = count(str, i, i);
            if (len > max_len) {
                max_len = len;
                len /= 2;
                auto center = i / 2;
                begin = center - (len / 2);
                end = center + len - (len / 2);
            }
        }
        return s.substr(begin, end - begin);
    }
};

4. Manacher（馬拉車）算法

思路：

馬拉車算法的大名不用介紹了吧，我只能說想出這算法的人真是個(gè)天才隐圾。

該算法可以看作是中心擴(kuò)展算法的一個(gè)優(yōu)化掂林，其點(diǎn)睛之筆在于利用了回文串的對(duì)稱性。

一圖勝千言：

圖1 馬拉車算法主要思想

當(dāng)前計(jì)算的字符我們稱為當(dāng)前點(diǎn)，如果當(dāng)前點(diǎn)落在了之前計(jì)算過的某個(gè)回文子串之內(nèi)，我們便可以利用關(guān)于回文子串中心對(duì)稱的那個(gè)對(duì)稱點(diǎn)，計(jì)算出當(dāng)前點(diǎn)回文子串的長度析桥。（只要小回文串完全落入回文串中，由于對(duì)稱性艰垂，兩個(gè)小回文串顯然是完全一致的泡仗，于是便可以跳過當(dāng)前點(diǎn)的計(jì)算）[情況1]

那從分類討論的角度來看，顯然還剩下兩種情況：

小回文串部分落入回文串猜憎，部分在回文串之外（當(dāng)前點(diǎn)還在回文串之內(nèi)）[情況2]
當(dāng)前點(diǎn)直接就超出了回文串的范圍[情況3]

針對(duì)[情況2]娩怎，我們可以利用對(duì)稱點(diǎn)先得到小回文串在回文串內(nèi)的長度，然后再利用中心擴(kuò)展算法求出小回文串在回文串外面部分的長度胰柑，二者相加就是完整的小回文串長度截亦。
針對(duì)[情況3]，由于無法利用對(duì)稱性柬讨，只能直接使用中心擴(kuò)展算法直接計(jì)算崩瓤。

是不是覺得簡(jiǎn)直天才？

上面的討論中我們提到需要判斷當(dāng)前點(diǎn)是否落入回文串之內(nèi)踩官，那我如何快速判斷是否落入了某個(gè)回文串內(nèi)呢却桶？
由于字符串從左往右遍歷，我們可以選擇已計(jì)算的右邊界索引最大的回文串作為圖中的回文串蔗牡。只要記錄下它的中心點(diǎn)和回文半徑颖系，就可以快速的判斷當(dāng)前點(diǎn)是否落入回文串內(nèi)，同時(shí)也可以快速判斷小回文串是全部落在回文串之內(nèi)辩越，還是只有部分落入嘁扼。
另外由于需要中心點(diǎn)、對(duì)稱點(diǎn)的回文半徑黔攒，所以我們可以采用一個(gè)數(shù)組保存全部字符的回文半徑趁啸。

時(shí)間復(fù)雜度 $O(n)$ ，空間復(fù)雜度 $O(n)$ 亏钩。

PS：講道理我不明白時(shí)間復(fù)雜度 $O(n)$ 是怎么算的莲绰，因?yàn)橹挥幸环N情況是可以完全利用對(duì)稱性的欺旧，其余兩種都需要做一定程度的中心擴(kuò)展姑丑。但由于對(duì)稱性的利用，我們可以確定最壞的情況也不過中心擴(kuò)展算法辞友，所以一定會(huì)比中心擴(kuò)展算法更快栅哀。

代碼：

class Solution {
public:
    string longestPalindrome(string s) {
        // 擴(kuò)展字符串震肮，這樣只需考慮奇子串了
        vector<char> str(s.size() * 2 + 1, '#');
        for (auto i = 0; i < s.size(); ++i)
            str[i * 2 + 1] = s[i];
        
        // 回文半徑數(shù)組
        vector<int> radius(str.size(), 0);
        // 以下四個(gè)變量都是在擴(kuò)展串中的，
        // max_c為回文串中心下標(biāo)留拾，max_r為回文串最右下標(biāo)戳晌，
        // ans_c為最長回文串中心下標(biāo)，ans_r為最長回文串回文半徑
        auto max_c = 0, max_r = 0, ans_c = 0, ans_r = 0;
        for (auto i = 0; i < str.size(); ++i) {
            // 計(jì)算當(dāng)前點(diǎn)回文半徑痴柔，分三種情況討論
            radius[i] = i < max_r ? min(radius[max_c * 2 - i], max_r - i) : 0;
            // 防止遇到情況2沦偎、情況3，修正當(dāng)前字符的回文半徑
            while (-1 < i - radius[i] && i + radius[i] < str.size() &&
                   str[i + radius[i]] == str[i - radius[i]])
                radius[i]++;
            // 由于上面循環(huán)會(huì)將形如"a"的小回文串設(shè)置回文半徑為1咳蔚，需修正
            radius[i]--;
            // 修正回文串半徑
            if (i + radius[i] > max_r) {
                max_c = i;
                max_r = i + radius[i];
            }
            // 修正最長回文串的中心和回文半徑
            if (radius[i] > ans_r) {
                ans_c = i;
                ans_r = radius[i];
            }
        }
        // 中心擴(kuò)展算法3.2中已經(jīng)推導(dǎo)過
        auto len = (ans_r * 2 + 1) / 2;
        auto center = ans_c / 2;
        auto begin = center - (len / 2);
        auto end = center + len - (len / 2);
        return s.substr(begin, end - begin);
    }
};

最后編輯于：2019.10.16 09:36:43

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末豪嚎，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子谈火，更是在濱河造成了極大的恐慌侈询，老刑警劉巖，帶你破解...
沈念sama閱讀 217,542評(píng)論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件糯耍，死亡現(xiàn)場(chǎng)離奇詭異扔字，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)温技，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,822評(píng)論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門革为，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人舵鳞，你說我怎么就攤上這事篷角。” “怎么了系任？”我有些...
開封第一講書人閱讀 163,912評(píng)論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵恳蹲，是天一觀的道長。經(jīng)常有香客問我俩滥，道長嘉蕾，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,449評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任霜旧，我火速辦了婚禮错忱，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘挂据。我一直安慰自己以清，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,500評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布崎逃。她就那樣靜靜地躺著掷倔，像睡著了一般。火紅的嫁衣襯著肌膚如雪个绍。梳的紋絲不亂的頭發(fā)上勒葱，一...
開封第一講書人閱讀 51,370評(píng)論 1贊 302
城市分裂傳說
那天浪汪，我揣著相機(jī)與錄音，去河邊找鬼凛虽。笑死死遭，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的凯旋。我是一名探鬼主播呀潭，決...
沈念sama閱讀 40,193評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼至非！你這毒婦竟也來了蜗侈？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,074評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤睡蟋，失蹤者是張志新（化名）和其女友劉穎踏幻，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體戳杀，經(jīng)...
沈念sama閱讀 45,505評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡该面，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,722評(píng)論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了信卡。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片隔缀。...
茶點(diǎn)故事閱讀 39,841評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖傍菇，靈堂內(nèi)的尸體忽然破棺而出猾瘸，到底是詐尸還是另有隱情，我是刑警寧澤丢习，帶...
沈念sama閱讀 35,569評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布牵触，位于F島的核電站，受9級(jí)特大地震影響咐低，放射性物質(zhì)發(fā)生泄漏揽思。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,168評(píng)論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一见擦、第九天我趴在偏房一處隱蔽的房頂上張望钉汗。院中可真熱鬧，春花似錦鲤屡、人聲如沸损痰。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,783評(píng)論 0贊 22
一樁弒父案酒来，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽卢未。三九已至，卻和暖如春役首，著一層夾襖步出監(jiān)牢的瞬間尝丐，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,918評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工衡奥，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留爹袁，地道東北人。一個(gè)月前我還...
沈念sama閱讀 47,962評(píng)論 2贊 370
代替公主和親
正文我出身青樓矮固，卻偏偏與公主長得像失息，于是被迫代替她去往敵國和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子档址，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,781評(píng)論 2贊 354