1 基本概念
- 串：是由零个或多个字符组成的优先序列，又名叫字符串。
- 本质是一种线性表的扩展，但更多的是关注子串的应用问题
- 子串在主串中的位置就是子串的第一个字符在主串中的序号。
字符编码
- ASCII：7位
- 拓展 ASCII：8位
- Unicode：16位
串的比较
- 挨个比较字符，以第一个不同的为序
- 前缀相同则短的小
2 存储结构
串的顺序存储结构
一般是用定长数组来定义，存在一个预定义的最大串长度。
- 实际的串长度保存在数组的 0 下标位置。
- 或在串值后面加一个不计入串长度的结束标记字符，比如"\0"
对于超出预定义的最大串长度的计算，串值的存储空间可在程序执行过程中动态分配
串的链式存储结构
与线性表相似，但为了不浪费空间，一个结点可存放多个字符，最后一个结点未占满时用"#"或其它非串值字符不全。
串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活 ，性能也不如顺序存储结构好。
3 字符串匹配
1)KMP 模式匹配算法
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”。减少了不必要的比较，比朴素的模式匹配算法效率提高了很多。
算法流程
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果 j = -1，或者当前字符匹配成功，都令i++，j++，继续匹配下一个字符；
- 如果 j != -1，且当前字符匹配失败，则令 i 不变，j = next[j]。
next 数组代表当前字符之前的字符串中，有多大长度的相同前缀后缀。
计算next 数组
next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀
//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
KMP代码
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
KMP的时间复杂度分析
文本串的长度为n，模式串的长度为m，匹配过程为O(n)，计算next为O(m)，KMP的整体时间复杂度为O(m + n)。
2)BM算法(更快)
Boyer-Moore算法，简称BM算法。
从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的时间复杂度。
BM算法定义了两个规则：
- 坏字符规则：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果"坏字符"不包含在模式串之中，则最右出现位置为-1。
- 好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。
3)Sunday算法(最快)
Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。
- 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；
- 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。