KONGJUNE / / ACM / 阅读量

## 马拉车算法思想

### 半径数组

$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12
$strM[i]$ # g # o # o # g # l # e #
$p[i]$ 1 2 1 2 5 2 1 2 1 2 1 2 1

for(int i=0; i < (int)str.length(); ++i) {
res += str[i];
res += "#";
}

/*数组*/
vector<int> p(res.length(), 0);
int mi = 0, right = 0;   //mi为最大回文串对应的中心点，right为该回文串能达到的最右端的值
int maxLen = 0, maxPoint = 0;    //maxLen为最大回文串的长度，maxPoint为记录中心点

for (int i = 1; i < res.length(); ++i){
p[i] = (right > i)? min(p[2 * mi - i], right - i) : 1;     //关键句，文中对这句以详细讲解

while(res[i + p[i]] == res[i - p[i]])
++p[i];

if(right < i + p[i])    //超过之前的最右端，则改变中心点和对应的最右端
{
right = i + p[i];
mi = i;
}

if(maxLen < p[i])     //更新最大回文串的长度，并记下此时的点
{
maxLen = p[i];
maxPoint = i;
}
}
return str.substr((maxPoint - maxLen) / 2, maxLen - 1);
}
{"ft_lang_label":"__label__zh","ft_lang_prob":0.9380151,"math_prob":0.99986637,"size":2870,"snap":"2020-34-2020-40","text_gpt3_token_len":2093,"char_repetition_ratio":0.10118632,"word_repetition_ratio":0.0154639175,"special_character_ratio":0.3770035,"punctuation_ratio":0.059183672,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99212784,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-09-21T06:39:25Z\",\"WARC-Record-ID\":\"<urn:uuid:f6a53104-203e-4b24-934c-48827eda77ec>\",\"Content-Length\":\"38529\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6100b6f8-e912-4462-8283-f7f62b5529f6>\",\"WARC-Concurrent-To\":\"<urn:uuid:b074ac40-5204-4eb1-b6d0-fb44249ee463>\",\"WARC-IP-Address\":\"123.57.255.126\",\"WARC-Target-URI\":\"https://blog.kongjune.com/manacher/\",\"WARC-Payload-Digest\":\"sha1:5OQJG327PHFSJBI6FZ6SW7ZTBZKVB6PA\",\"WARC-Block-Digest\":\"sha1:Y7OECZUDS6VV22WOW62LIORZNTN264XF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-40/CC-MAIN-2020-40_segments_1600400198942.13_warc_CC-MAIN-20200921050331-20200921080331-00021.warc.gz\"}"}