云南疫情最新消息今天/网站seo外包靠谱吗

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入: “aacecaaa”
输出: “aaacecaaa”
示例 2:
输入: “abcd”
输出: “dcbabcd”
来源：力扣（LeetCode）

题目分析

s1 表示 s 的反转字符串。题目可以转换为查找 s1 的后缀和 s 的前缀最长重合的部分，即用 s 去匹配 s1 即可，s 的匹配剩余部分加到 s1 末尾即可。

代码示例

class Solution {
public:string shortestPalindrome(string s) {string rs = s;reverse(rs.begin(),rs.end());//用 s 做模版去匹配 rsvector<int> next (s.size(),0);getNext(s,next);int p = 0;//执行模版开头for(int i = 0;i < rs.size();i++){while( rs[i] != s[p] && p > 0){p = next[p];}if( rs[i] == s[p]){p++;}}string endfix = "";if( p < s.size() )endfix =  s.substr(p);return rs+endfix;}void getNext(const string &pattern,vector<int> &next){if( next.size() <= 2) return;//已匹配长度为 0 或者 1 时，最长前后缀长度 为 0next[0] = 0;next[1] = 0;int index = 0;// 模版中已经匹配的长度，即下一个要匹配的元素下标int maxPrefixlen = 0;// 已匹配模版的最长前后缀长度，即最长前后缀下一个元素下标for( index = 2;index < pattern.size();index++){while( pattern[maxPrefixlen] != pattern[index-1] && maxPrefixlen > 0){maxPrefixlen = next[maxPrefixlen];//回退}//新增的已匹配元素下标是 index-1if( pattern[maxPrefixlen] == pattern[index-1] ){maxPrefixlen++;//已匹配长度加1}next[index] = maxPrefixlen;}}
};

KMP 算法

1. 基本思想
   KMP 算法的核心思想就是充分利用已匹配过的字符串信息，减少重复的字符比较；匹配过程中主字符串不动，挪动模式字符串。
   
   如上图所示：当主字符串匹配到位置 i、模式字符串匹配到位置 j 时，这之前的位置都是匹配的，但 i 和 j 对应字符不匹配。
   通过观察可知主字符串的后缀和模式字符串的前缀存在重合部分，此时直接挪动模式字符串使 j 回退到 k 的位置，则重合部分可以不用重新匹配，从 j 往后继续匹配即可。
   由以上过程可知：在匹配过程中出现不能匹配的情况了，就把模式串当前的位置 j 回退到已匹配字符串的最大前后缀的下个位置即可。
   模式串中每个位置的回退规则只和模式串自身有关，即可以提前对数据进行预处理，先把每个位置的回退对应关系得到，在匹配过程中就可以直接使用。
2. next 数组含义
   由上图可知：j 是模式串中已经匹配的字符串的下个位置的下标、k 是模式串中已经匹配的字符串中最大前后缀的下个位置的下标、k 就是 j 到回退到的位置。
   next 数组就是用来记录 j 和 k 的对应关系。数组的下标就 j ：模式串中已经匹配的字符串的下个位置的下标；数组的值就是 k ：模式串中已经匹配的字符串中最大前后缀的下个位置的下标。
3. next 数组实现

void getNext(const string &pattern, vector<int> & next)
{next[0] = 0;next[1] = 0;//已匹配长度为0、1 时，最大前后缀长度都是 0int maxPrefixlen = 0;//当前最大前后缀长度、即指向最大前后缀的下个位置int index = 0;//已经匹配的长度、指向已匹配的下个位置for (index = 2; index < pattern.size(); ++index){//新加入的匹配元素是 index-1while ( pattern[index - 1] != pattern[maxPrefixlen] && maxPrefixlen > 0 ){maxPrefixlen = next[maxPrefixlen];}if (pattern[index-1] == pattern[maxPrefixlen]){maxPrefixlen++;}next[index] = maxPrefixlen;}
}

5. kmp 算法实现

bool kmp(const string &text, const string &pattern)
{vector<int> next(pattern.size(), 0);getNext(pattern, next);int p = 0;for (int i = 0; i < text.size(); i++){while (text[i] != pattern[p] && p > 0){p = next[p];}if ( text[i] == pattern[p]){p++;}if (p == pattern.size()){return true;}}
​
}