当前位置：首页 > news >正文

代码随想录二刷|字符串总结

news 来源：原创 2025/6/19 8:19:06

代码随想录二刷|字符串

反转数字

题干

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

思路

class Solution {
public:void reverseString(vector<char>& s) {int n=s.size();int l=0;int r=n-1;while(l<r){char temp=s[l];s[l]=s[r];s[r]=temp;l++;r--;}}
};

反转数字II

题干

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

思路

class Solution {
public:string rev(string s, int l, int r) {while (l < r) {char temp = s[l];s[l] = s[r];s[r] = temp;l++;r--;}return s;}string reverseStr(string s, int k) {int n = s.size();for (int i = 0; i < n; i += 2 * k) {if (i + k > n) {return rev(s, i, n - 1);} else if (i + 2 * k > n) {return rev(s, i, i + k - 1);}s = rev(s, i, i + k - 1);}return s;}
};

替换数字

题干

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

思路

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;cin>>s;int n=s.size();int l=0;string res;while(l<n){if(s[l]-'a'>=0 && s[l]-'a'<=26) {res.push_back(s[l]);l++;}else{res+="number";l++;}}cout<<res;return 0;
}

KMP算法

解决的问题：字符串匹配

例如：文本串aabaabaaf，模式串aabaaf，问文本串里面是否出现过模式串

概述

文本串aabaabaaf，

模式串aabaaf

发现f和b不匹配，找到前面匹配上的子串中的b，从b开始向后匹配

理论

1、寻找新的匹配起点

找模式串的最长相等前后缀，前缀的后一个字符作为新的匹配起点

2、前缀和后缀

（1）前缀：包含首字母不包含尾字母的所有子串

（2）后缀：包含尾字母不包含首字母的所有子串

3、前缀表

模式串的各个子串的最长相等前后缀长度的列表

a:0 aa: 1 aab: 0 aaba: 1 aabaa:2 abaaf:0

前缀表[0,1,0,1,2,0]

4、使用前缀表的匹配

（1）找模式串里面冲突的字符之前的子串前缀表里面的最长相等前后缀

（2）最长的相等前后缀长度就是新的匹配起点的下标

在f这个位置发生冲突，在f之前最长的相等前后缀长度为2，在子串aabaa中出现，跳到下标为2的位置，从b开始继续匹配

5、next数组

next数组可以是前缀表，或者前缀表统一减1，或者整体后移的结果

实现

1、next数组不同实现及其处理

（1）选择前缀表作为next数组

（2）在下标为i处遇见冲突，找next[i-1]

（3） j=next[i-1]，模式串从[j]往后的部分作为新的模式串进行匹配

注：如果next数组是前缀表右移一位，第一位赋值-1，那么在下标为i处遇见冲突，找next[i]；如果next数组是前缀表 -1，那么在下标为i处遇见冲突，找next[i-1]+1

2、求next数组

符号：

j：指向前缀末尾位置（前缀最后一个字符）

i：指向后缀末尾位置

（i相当于例子里面的f的下标，j相当于例子里面b的下标）

s：模式串

由于不能确定以j结尾的前缀和以i结尾的后缀是不是最长相等前后缀，在遍历的时候，j不是i及i以前最长相等前后缀的长度。

但是j既然走到了这里，就说明以j-1结尾的前缀和以i-1结尾的后缀是最长相等前后缀，j-1是s[0,i-1]这个子串最长相等前后缀的长度

1）初始化：

j初始化为0，next[0]=0

2）处理前后缀不相同的情况

前后缀不相等，就是s[i]!=s[j]

此时令 j=next[j-1]，让j向左回退，退到j以前最长相等前后缀对应的的前缀末尾，再与原后缀末尾[i]进行比较

不停处理，直到前后缀相等，所以用while

while (j>0&&s[i]!=s[j]){j=next[j-1];}

3）处理前后缀相同的情况

如果 s[i]==s[j]，说明前后缀相同,i及i以前最长相等前后缀的长度+1

j++，next[i]=j

4）更新next数组（在 2）和3）中各自进行）

for (i=1;i<模式串长度;i++){while (j>0&&s[i]!=s[j]){j=next[j-1];}if(s[i]==s[j]){j++;}next[i]=j;}

3、用next数组进行匹配

i为文本串t的下标

j为模式串s的下标

遍历i

（1）如果匹配，也就是if(s[j]==t[j])，让j++

（2）如果不匹配，也就是while(s[j]!=t[i])，让 j=next[j-1]

如果j=s.size()了，那么说明匹配了，匹配的起点是i-j+1

如果i先到终点，说明没匹配

KMP字符串匹配模版题：找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1

class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size();int m = needle.size();vector<int> next(m, 0);int j = 0;for (int i = 1; i < m; i++) {while (j > 0 && needle[j] != needle[i]) {j = next[j - 1];}if (needle[j] == needle[i]) {j++;}next[i] = j;}j = 0;for (int i = 0; i < n; i++) {while (j > 0 && needle[j] != haystack[i]) {j = next[j - 1];}if (needle[j] == haystack[i]) {j++;if (j == m)return i - j + 1;}}return -1;}
};

KMP总结

问题：文本串t中是否出现了模式串s

匹配思路：

i是文本串下标

j是模式串下标

next数组存放模式串前k个元素的最长相等前后缀的长度：例如next[k]，表示模式串从s[0]到s[j]这部分子串的最长相等前后缀的长度

遍历i

（1）如果s[j]与t[i]匹配，i++

（2）如果s[j]与t[i]匹配，j=next[j-1]：

因为在j处没有和文本匹配，而next[j-1]是[0,j-1]这一段里最长相等前后缀的长度，也是这一段最长相等前后缀当中的前缀的后一个元素下标。不停地这样做，直到匹配或j退回0。

这个操作的含义是：如果j不能和i匹配，那么去找j前面有可能匹配的。

=既然能j能到这里，那么说明，现在s[0,j-1]和t[i-j，i-1]是匹配的，如果挨着s[j]的元素在模式串的开头已经出现过，那么可以接着开头出现的元素继续遍历，而不是从模式串的开头开始遍历。

如果j前面有相等的前后缀，那么取最长的相等前缀后面的那个下标为新的j，看看能不能从这里开始匹配；如果没有的话就只能从0开始

e.g.

abcabdef：到d那里匹配不上，可以退回c那里，如果现在的t[i]正好是c，那么相当于已经匹配好abc，继续向下即可

abcdf：到d那里匹配不上，t里面i前面挨着的是abc，模式串只能从a开始了

（3）如果j到达s.size()，那么说明匹配了，如果i先到达终点，说明

求next数组的思路

i是模式串后缀的最后一个元素（子串最后一个元素）

j是模式串前缀的最后一个元素

（因为现在前后缀还不一定相等，因此j不是s[0,i]的最长相等前后缀长度，现在的最长相等前后缀长度是j-1）

从1开始遍历i

（1）如果前后缀相等，也就是s[i]==s[j]，前缀继续增长，j++

（2）如果前后缀不相等，那么j=next[j-1]，重复这样做，直到s[i]==s[j]或j为0

这样的意思是，现在已经知道前后缀最后一位不相等了，向前寻找更短的前缀。j既然走到了这里，就说明以j-1结尾的前缀和以i-1结尾的后缀是最长相等前后缀。[0,j-1]的子串中，前缀等于后缀，后缀等于y以i-1结尾的串（s[0,i-1]的后缀的后缀）（s[0,i-1]前缀的后缀等于s[0,i-1]后缀的后缀）。所以向前找到s[0,j-1]内最长相等前后缀的前缀的后一个元素，接着前缀继续和后面比较。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

（3）next[i]=j：因为++前的j是前缀的最后一位下标，并且前后缀相同，并且进过了++，现在的最长相等前后缀长度是j

重复子串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成

暴力

搜索子串：子串开头是第一个元素，只需要遍历子串结束的位置

因此只需要两次for循环

移动匹配

重复子串x组成的字符串s，可以切成3份：x 中间 x

一个s和另一个s拼接起来，如果去掉前一个的首元素，后一个的尾元素后，剩下的部分中包含s（前一个s的后面和后一个s的前面拼接起来可以得到s），那么就是s就是由重复子串组成的

判断剩下的部分中是否包含s可以用KMP或调库用find函数

class Solution {
public:bool repeatedSubstringPattern(string s) {string s2=s+s;// auto it=s2.begin();s2.erase(s2.begin());s2.erase(s2.end()-1);return s2.find(s)!=string::npos;}
};
用KMP实现find，判断剩下的部分中是否包含s

KMP

结论：如果字符串是由重复子串构成的，那么它的最小重复子串是最长相等前后缀不包含的那部分

-----------|—

—|------------

---------- 是最长相等前后缀 —是最小重复子串

证明

充分性证明

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

必要性证明：即证何时最长相等前后缀不包含的部分是最小重复子串

发现只有在四则被最长相等前后缀不包含的部分长度整除时，最长相等前后缀不包含的部分才会是最小重复子串

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

求解

next[size-1]是最长相等前后缀的长度，size-next[size-1]最长相等前后缀不包含的部分长度，如果size被这个长度整除，那么最长相等前后缀不包含的部分是最小重复子串

class Solution {
public:bool repeatedSubstringPattern(string s) {int n=s.size();if(n==0)return false;vector<int>next(n,0);int j=0;for(int i=1;i<n;i++){while(j>0&&s[j]!=s[i])j=next[j-1];if(s[j]==s[i])j++;next[i]=j;}int len=next[n-1];if(len!=0&&n%(n-len)==0)return true;return false;}
};

string类库函数

erase：传入迭代器，删除对应位置的元素，无返回值（其他的容器的erase也是这么用）

find：传入一个字符串s，判断s有没有在字符串里面出现，不出现的话返回string::npos，出现的话返回s出现处的下标

ctornext(n,0);
int j=0;
for(int i=1;i<n;i++)
{
while(j>0&&s[j]!=s[i])j=next[j-1];
if(s[j]==s[i])j++;
next[i]=j;
}
int len=next[n-1];
if(len!=0&&n%(n-len)==0)return true;
return false;
}
};


## string类库函数erase：传入迭代器，删除对应位置的元素，无返回值（其他的容器的erase也是这么用）find：传入一个字符串s，判断s有没有在字符串里面出现，不出现的话返回string::npos，出现的话返回s出现处的下标