字符串
1. 常用标准串函数
| 函数名 | 函数功能说明 |
|---|---|
| size_t strlen(char* s) | 返回s的长度 |
| char* strcpy(char* s1, const char* s2) | 将字符串s2复制到s1，并返回s1的指针 |
| char* strcat(char* s1, const char* s2) | 将字符串s2拼接到s1尾部 |
| int strcmp(const char* s1, const char* s2) | 比较s2和s1，s1大于s2返回正数 |
| char* strchr(char* s, char c) | 返回s中第一次出现c的位置，如果没有c则返回NULL |
| char* strrchr(char* s, char c) | 从s的尾部开始找第一次出现c的位置 |
String类里面的函数：
2. 字符串的模式匹配（Pattern matching）
? 所谓模式匹配，是指在文本T（text）中寻找一种特定的模式P（pattren），比如PDF等文档文件中常用的“查找”操作。
? 模式匹配又分 精准匹配 和 近似匹配 两种。
2.1. 朴素的模式匹配算法
? 基本思想是将P从T的开始进行匹配，如果“失配”则向后移动一位。
int NaiveStrMatching(const string T, const string P){
int i = 0;//P的索引
int j = 0;//T的索引
int len_i = P.length();
int len_j = T.length();
if(len_i >= len_j) return -1;
while(i<len_i && j<len_j){
if(T[j]==P[i]){
j++;i++;
}
else{
j = j-i+1;
i = 0;
}
}
if(i>=len_i) return j-i+1;
return -1;
}
? 若设P的长度为M，T的长度为N。该算法最差的时间复杂度为O(M*N).
2.2. KMP模式匹配算法
字符串的特征向量
? 在朴素的模式匹配算法中，存在大量没有必要的回溯。如下图中，在T[3]处发生失配，按照朴素的模式匹配法，会将P一步步移动至完全匹配，且每次匹配都会从头开始匹配。但这并不是必要的，我们完全可以直接将P移动到失配的位置开始匹配。
? KMP算法通过定义next数组来计算发生失配时，应从P的哪个位置继续匹配。在KMP算法中，不存在T的回溯。next[i]定义如下为子串P[0:i]（不包括P[i]）的前缀子串与后缀子串的最大匹配数。且定义next[0] = -1。比如：
| P | a | b | a | a | b | a |
|---|---|---|---|---|---|---|
| next[i] | -1 | 0 | 1 | 0 | 1 | 2 |
? 另一种对next数组更好的理解是，当P[i]与T[j]发生失配时，应使用P[next[i]]来与T[j]进行匹配。（根据next[i]的定义可知，next[i]之前的位置肯定是能匹配上的，不需要再对j进行回溯）。
? 求解next数组的方法如下：
//求next数组
int *findNext(string P){
int i = 0;
int k = -1;
int len = P.length();
int *next = new int [len];
next[0] = -1;
while(i < len-1){ //注意不是i < len.
while(k != -1 && P[i]!=P[k]){
k = next[k];
//这一段看了好久才理解。这其实也是一个KMP的模式匹配，是P的前缀与P的后缀的匹配。
}
i++;
k++;
next[i]=k;
//注意next的定义是i之前的最大前缀后缀匹配数，所以i要加一；由于P[i]==P[k]，所以要加一
}
}
? 这种next的定义仍有不好的地方。当碰到连续相同的字母时，时间消耗会增加。比如如下情况：
? 这种时候，很明显由于P[2]==P[0]，而P[2]失配，所以P[2]必然失配，所以完全可以直接跳到next[2].
? 优化的next数组的求解如下（此时的next的定义不再是前缀后缀匹配数，而是当i处失配时，应和T[i]进行匹配的元素）：
//优化的next数组的求算
int* findNext(string P){
int i = 0;
int k = -1;
int len = P.length();
next[0] = -1;
while(i<len-1){
while(k!=-1 && P[i]!=P[k]){
k = next[k];
}
i++;
k++;
if(P[i]==P[k]){
next[i] = next[k];//优化
}
else{
next[i] = k;
}
}
}
KMP模式匹配算法
int KMPStrMatching(string T, string P, int* next){
int i = 0;
int j = 0;
int lenp = P.string();
int lent = T.string();
if(lent < lenp) return -1;
while(i < plen && j < tlen){
if(i==-1 || P[i]==P[j]){
i++;j++;//i=-1的时候，意味着与j匹配永远是失败的。直接从j+1开始重新匹配。
}
else{
i = next[i];
}
if(i == plen){
return j - plen + 1;
}
return -1;
}