字符串

字符串的实现（C++实现）

实现字符串的构造及其常用的接口函数，深入掌握理解字符串的实现

C++ / STL 中string实现了字符串的标准类库，可作为参考

1. 两个私有成员
   char *ch; 按串长动态分配存储区
   int length; 串长
2. 3个构造函数，1个析构函数，13个常用函数接口

补充哦！！！

---

---

字符串的模式匹配算法

What is 字符串的模式匹配 ?：（举个栗子）
主串：00101100010021010
模式串：0001
模式匹配就是在主串中匹配模式串，可以视为定位操作，若存在，返回匹配成功（以及返回主串中第一个匹配的首位置）；否则返回匹配失败

1. 朴素模式匹配算法（BF算法－蛮力求解）

举个栗子：BF蛮力匹配的过程
主串 str : ABABCABCACBAB
模式串 substr : ABCAC

BF算法匹配流程

分析：

这种方法的特点就是简单，容易理解实现
但是BF算法的最大问题就是主串的字符匹配指针（下标）总是要回溯，在出现比较多的字符匹配但又不是完全匹配时，回溯更多，显得效率低下
例如：
str : 00000000000000000000000000000001
substr : 00001

代码实现

int FindFirstmatchIndex(string str, string substr)
{
    int i = 0;
    int j = 0;

    while (i<str.length && j<substr.length)
    {
        if (str[i] == substr[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 1;       //回溯主串匹配指针
            j = 0;               //模式串指针回溯
        }
    }

    if (j == substr.length)
    {
        return i-j;
    }
    else
    {
        return -1;
    }
}

2. KMP算法

与BF算法相比的改进处：每当一趟匹配过程中出现字符比较不等时，主串的指针不需要回溯，此时利用已经得到的"部分匹配"结果，将模式串尽量的向右移，继续进行匹配比较。
关键： 模式串尽量右移，右移多少距离就是KMP算法的关键，换句话说就是当主串的第i个字符与模式串的第j个字符失配时，主串的第i个字符应与模式串的哪一个字符再比较（这里就是KMP算法的精华：求Next数组）

KMP算法比较经典，在很多字符串问题中都有其思想的应用，故新开一篇进行整理

KMP算法