孟习笔谈
字符串进阶
发布时间:
字符串基础
字符串定义
字符串，就是由字符连接而成的序列。
常见的字符串问题包括字符串匹配问题、子串相关问题、前缀/后缀相关问题、回文串相关问题、子序列相关问题等。
字符串标准库
C++ 标准库 C++ 标准库操作字符串对象 std::string，同时也提供对字符数组的兼容。
参见：std::basic_string、std::basic_string_view
js
重载了赋值运算符 +，当 + 两边是 string/char/char[]/const char* 类型时，可以将这两个变量连接，返回连接后的字符串（string）。
赋值运算符 = 右侧可以是 const string/string/const char*/char*。
访问运算符 [cur] 返回 cur 位置的引用。
访问函数 data()/c_str() //返回一个 const char* 指针，内容与该 string 相同。
容量函数 size() //返回字符串字符个数。
find(ch, start = 0) //查找并返回从 start 开始的字符 ch 的位置；rfind(ch) 从末尾开始，查找并返回第一个找到的字符 ch 的位置（皆从 0 开始）（如果查找不到，返回 -1）。
substr(start, len) //可以从字符串的 start（从 0 开始）截取一个长度为 len 的字符串（缺省 len 时代码截取到字符串末尾）。
append(s) //将 s 添加到字符串末尾。
append(s, pos, n) //将字符串 s 中，从 pos 开始的 n 个字符连接到当前字符串结尾。
replace(pos, n, s) //删除从 pos 开始的 n 个字符，然后在 pos 处插入串 s。
erase(pos, n) //删除从 pos 开始的 n 个字符。
insert(pos, s) //在 pos 位置插入字符串 s。
std::string //重载了比较逻辑运算符，复杂度是 \Theta(N) 的。
更详细用法与更多库和代码实现请看 https://zh.cppreference.com/w/cpp/string/basic_string
字符串匹配问题
定义
该问题可以概括为「给定字符串 S 和 T，在主串 S 中寻找子串 T」。字符 T 称为模式串 $ (pattern) $。
类型
js
**单串匹配**：给定一个模式串和一个待匹配串，找出前者在后者中的所有位置。
**多串匹配**：给定多个模式串和一个待匹配串，找出这些模式串在后者中的所有位置。
出现多个待匹配串时，将它们直接连起来便可作为一个待匹配串处理。 可以直接当做单串匹配，但是效率不够高。
其他类型：例如匹配一个串的任意后缀，匹配多个串的任意后缀……
暴力做法
简称 BF (Brute Force) 算法。该算法的基本思想是从主串 S 的第一个字符开始和模式串 T 的第一个字符进行比较，若相等，则继续比较二者的后续字符；否则，模式串 T 回退到第一个字符，重新和主串 S 的第二个字符进行比较。如此往复，直到 S 或 T 中所有字符比较完毕。
实现 代码部分
js
/*
* s：待匹配的主串
* t：模式串
* n：主串的长度
* m：模式串的长度
*/
std::vector<int> match(char *s, char *t, int n, int m) {
std::vector<int> ans;
int i, j;
for (i = 0; i < n - m + 1; i++) {
for (j = 0; j < m; j++) {
if (s[i + j] != t[j]) break;
}
if (j == m) ans.push_back(i);
}
return ans;
}
kmp
kmp简介
一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和$ ptr $长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。
KMP算法：可以实现复杂度为$ O(m+n) $
为何简化了时间复杂度： 充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量）。 上面理不理解无所谓，我说的其实也没有深刻剖析里面的内部原因。
代码模版
js
int KMP(char *str, int slen, char *ptr, int plen)
{
int *next = new int[plen];
cal_next(ptr, next, plen);//计算next数组
int k = -1;
for (int i = 0; i < slen; i++)
{
while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）
k = next[k];//往前回溯
if (ptr[k + 1] == str[i])
k = k + 1;
if (k == plen-1)//说明k移动到ptr的最末端
{
//cout << "在位置" << i-plen+1<< endl;
//k = -1;//重新初始化，寻找下一个
//i = i - plen + 1;//i定位到该位置
return i-plen+1;//返回相应的位置
}
}
return -1;
}
扩展KMP
扩展KMP：
给出模板串A和子串B，长度分别为lenA和lenB，要求在线性时间内，对于每个A[i]（0<=i<lenA)，
求出A[i..lenA-1]与B的最长公共前缀长度，记为ex[i]（或者说，ex[i]为满足A[i..i+z-1]==B[0..z-1]的最大的z值）。
扩展KMP可以用来解决很多字符串问题，如求一个字符串的最长回文子串和最长重复子串。
算法
设next[i] 为满足B[i..i+z-1]==B[0..z-1] 的最大的z值（也就是B的自身匹配）。设目前 next[0..lenB-1]与ex[0..i-1]``` 均已求出，要用它们来求ex[i]的值。
设p为目前A串中匹配到的最远位置，k为让其匹配到最远位置的值（或者说，k是在0<=i0<i的所有i0值中，使i0+ex[i0]-1的值最大的一个，p为这个最大值，即k+ex[k]-1·）。 显然，p之后的所有位都是未知的，也就是目前还无法知道A[p+1..lenA-1]中的任何一位和B的任何一位是否相等。 根据ex的定义可得，A[k..p]==B[0..p-k]，因为i>k，所以又有A[i..p]==B[i-k..p-k]，设L=next[i-k]，则根据next的定义有B[0..L-1]==B[i-k..i-k+L-1]。考虑i-k+L-1与p-k的关系：
（1）i-k+L-1<p-k，即i+L<=p。这时，由A[i..p]==B[i-k..p-k]可以得到A[i..i+L-1]==B[i-k..i-k+L-1]，又因为B[0..L-1]==B[i-k..i-k+L-1]所以A[i..i+L-1]==B[0..L-1]，这就说明ex[i]>=L。又由于next的定义可得，A[i+L]必然不等于B[L]（否则A[i..i+L]==B[0..L]，因为i+L<=p，所以A[i..i+L]==B[i-k..i-k+L]，这样B[0..L]==B[i-k..i-k+L]，故next[i-k]的值应为L+1或更大），这样，可以直接得到ex[i]=L！
（2）i+k-L+1>=p-k，即i+L>p。这时，首先可以知道A[i..p]和B[0..p-i]是相等的（因为A[i..p]==B[i-k..p-k]，而i+k-L+1>=p-k，由B[0..L-1]==B[i-k..i-k+L-1]可得B[0..p-i]==B[i-k..p-k]，即A[i..p]==B[0..p-i]），然后，对于A[p+1]和B[p-i+1]是否相等，目前是不知道的（因为前面已经说过，p是目前A串中匹配到的最远位置，在p之后无法知道任何一位的匹配信息），因此，要从A[p+1]与B[p-i+1]开始往后继续匹配（设j为目前B的匹配位置的下标，一开始j=p-i+1，每次比较A[i+j]与B[j]是否相等，直到不相等或者越界为止，此时的j值就是ex[i]的值）。在这种情况下，p的值必然会得到延伸，因此更新k和p的值。 边界：ex[0]的值需要预先求出，然后将初始的k设为0，p设为ex[0]-1。
对于求next数组，也是“自身匹配”，类似KMP的方法处理即可。唯一的不同点也在边界上：可以直接知道next[0]=lenB，next[1]的值预先求出，然后初始k=1，p=ex[1]。
需要严重注意的是，在上述的情况（2）中，本该从A[p+1]与B[p-i+1]开始匹配，但是，若p+1<i，也就是p-i+1<0（这种情况是有可能发生的，当ex[i-1]=0，且前面的ex值都没有延伸到i及以后的时候）的话，需要将A、B的下标都加1（因为此时p必然等于i-2，如果A、B的下标用两个变量x、y控制的话，x和y都要加1）！！
时间复杂度分析
在KMP和扩展KMP中，不管是A串还是B串，其匹配位置都是单调递增的，故总时间复杂度是线性的，都为O(lenA + lenB)（只是扩展KMP比KMP的常数更大一些）。
应用
KMP和扩展KMP在解决字符串问题中有大用。很多看上去很猥琐的字符串问题，都可以归结到这两种算法之中。另外，这里的“字符串”可以延伸为一切类型的数组，而不仅仅是字符数组。
代码模版
js
#include<iostream>
using namespace std;
const int N = 101010;
int next[N],extand[N];
void getnext(char *T){// next[i]: 以第i位置开始的子串 与 T的公共前缀
int i,length = strlen(T);
next[0] = length;
for(i = 0;i<length-1 && T[i]==T[i+1]; i++);
next[1] = i;
int a = 1;
for(int k = 2; k < length; k++){
int p = a+next[a]-1, L = next[k-a];
if( (k-1)+L >= p ){
int j = (p-k+1)>0? (p-k+1) : 0;
while(k+j<length && T[k+j]==T[j]) j++;// 枚举(p+1，length) 与(p-k+1,length) 区间比较
next[k] = j, a = k;
}
else next[k] = L;
}
}
void getextand(char *S,char *T){
memset(next,0,sizeof(next));
getnext(T);
int Slen = strlen(S), Tlen = strlen(T), a = 0;
int MinLen = Slen>Tlen?Tlen:Slen;
while(a<MinLen && S[a]==T[a]) a++;
extand[0] = a, a = 0;
for(int k = 1; k < Slen; k++){
int p = a+extand[a]-1, L = next[k-a];
if( (k-1)+L >= p ){
int j = (p-k+1)>0? (p-k+1) : 0;
while(k+j<Slen && j<Tlen && S[k+j]==T[j] ) j++;
extand[k] = j;a = k;
}
else extand[k] = L;
}
}
int main(){
char s[N],t[N];
while(~scanf("%s %s",s,t)){
getextand(s,t);
for(int i = 0; i < strlen(t); i++)
printf("%d ",next[i]);
puts("");
for(int i = 0; i < strlen(s); i++)
printf("%d ",extand[i]);
puts("");
}
}