题目： 151.翻转字符串里的单词（没做出来）
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
没写出来说明我对于双指针的理解还是不够透彻，这里重新复习一遍。快指针的作用是用于获取我们所需要元素的位置，而慢指针的作用是用于获取我们想要将元素安放的位置
思路：本体的难点是在不使用erase函数的前提下，在o(1)复杂度的前提下完成多余空格的删减，下面是代码过程，用fast指针找到单词的开头后通过slow指针确定所要存放的位置。需要注意的是第一个单词前不需要加空格而后面的单词前都需要加空格。
void removeExtraSpace(string& s){
int slow = 0;
for(int fast = 0; fast<s.size();++fast){
if(s[fast] != ' ') //找到单词的开头
{
if(slow != 0){ //判断是否是第一个单词，如果是则不用再单词前面加空格，如果是则需要加空格
s[slow++] = ' ';
}
while(fast < s.size() && s[fast] != ' '){ //将整个单词放到新的位置
s[slow++] = s[fast++];
}
}
}
s.resize(slow);
}完整代码：
class Solution {
public:
void removeExtraSpace(string& s){
int slow = 0;
for(int fast = 0; fast<s.size();++fast){
if(s[fast] != ' ') //找到单词的开头
{
if(slow != 0){ //判断是否是第一个单词，如果是则不用再单词前面加空格，如果是则需要加空格
s[slow++] = ' ';
}
while(fast < s.size() && s[fast] != ' '){ //将整个单词放到新的位置
s[slow++] = s[fast++];
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
removeExtraSpace(s);
reverse(s.begin(),s.end());
int start = 0;
for(int i = 0; i<= s.size();i++){
if(s[i] == ' ' || i == s.size()){
reverse(s.begin()+start, s.begin()+i);
start = i+1;
}
}
return s;
}
};题目：右旋字符串
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出：输出共一行，为进行了右旋转操作后的字符串。
样例输入：
2
abcdefg 1 2
样例输出：
fgabcde1
数据范围：1 <= k < 10000, 1 <= s.length < 10000;
思路：将字符分成两个部分，两个部分分别反转，之后再将整个字符串反转得到结果。
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main ()
{
string s;
int K;
cin>> K>>s;
reverse(s.end()-K,s.end());
reverse(s.begin(),s.end()-K);
reverse(s.begin(),s.end());
cout << s;
}KMP算法
前缀
不包含尾元素的，只包含首元素的所有子串
例如：aabaaf,其首元素为a，尾素为f因此其前缀为a,aa,aab,aaba,aabaa;
后缀
和前缀相反，其是只包含尾元素不包含首元素的所有字串
例如：aabaaf,其首元素为a，尾素为f因此其后缀为f,af,aaf,baaf,abaaf;
最长相等前后缀
最长相等前后缀的值可以表示为：值为多少就是有多少位的后缀就有多少位的前缀与之匹配。
例如：
a的最长相等前后缀为0；
aa 的最长相等前后缀为1；
aab 的最长相等前后缀为0；
aaba 的最长相等前后缀为1；
aabaa 的最长相等前后缀为2；
aabaaf 的最长相等前后缀为0；
前缀表
那上面aabaaf为例子，其前缀表为上面最长相等前后缀的值即为010120
使用前缀表匹配的过程例子：
文字串：aabaabaaf
模式串：aabaaf
此时模式串的前缀表为010120，当匹配到文字串的第5b位发现匹配不上了，此时可以查看aabaa的前缀表中的值为2，因此说明前缀中的前两位和aabaa后缀的两位是相同的，因此回到aa的后一位来进行匹配及2位置，之后继续匹配。
next数组
就是将前缀表右移或左移以方便代码实现。
next数组的代码实现
构造next数组
我们定义一个函数getNext来构建next数组，函数参数为指向next数组的指针，和一个字符串。 代码如下：
void getNext(int* next, const string& s)构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：（习惯了代码随想录视频中的节奏因此本文中使用的next数组就是前缀和，没有右移动或将其实位置变为-1）
初始化
处理前后缀不相同的情况
处理前后缀相同的情况
void getNext(int* next,const string& s){
//初始化
int j = 0;
next[0] = j;
for(int i = 1;i<s.size();i++){
//处理前后缀不相同的情况（此处用while是因为可能会进行多次的回退而不仅仅是一次）
while(j>0 && s[j] != s[i]){
j = next[j-1];
}
//处理前后缀相同的情况
if(s[i] == s[j]){
j++;
}
next[i] = j;
}
}KMP算法题目：28. 实现 strStr()
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
思路：KMP算法得到next数组后进行操作
class Solution {
public:
void getNext(int* next,const string& s){
int j = 0;
next[0] = j;
for(int i = 1;i<s.size();i++){
//判断不相等的情况
while(j>0 && s[j] != s[i]){
j = next[j-1];
}
if(s[i] == s[j]){
j++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if(needle.size() == 0){
return 0;
}
vector<int>next(needle.size());
getNext(&next[0], needle);
int j = 0;
for(int i = 0; i< haystack.size();i++){
while(j > 0 && haystack[i] != needle[j]){
j = next[j-1];
}
if(haystack[i] == needle[j]){
j++;
}
if(j == needle.size()){ // j 移动到needle的末尾说明已经找到了
return (i - needle.size() + 1);
}
}
return -1;
}
};
评论