【有书共读】《算法与数据结构题目最优解》（在线编程题总结5）

int Index(string S, string T, int pos){
    //返回子串T在主串S中第pos个字符之后的位置，若不存在，则函数值为0
    //其中，T为空，1<=pos<=S.length()
    int i = pos;
    int j = 1;
    while (i <= S[0] && j <= T[0]){
        if (S[i] == T[j]){
            ++i;++j;//继续比较后续字符
        }
        else{
            i = i - j + 2;//指针后退重新开始匹配
            j = 1;
        }
    }
    if (j > T[0])
        return i - T[0];
    else
        return 0;
}//Index

3.2 KMP算法

       KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息（已经匹配的部分中的对称信息），尽量减少模式串（待搜索词）与文本串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，该函数本身包含了模式串的局部匹配信息。其时间复杂度为O（n+m）。详细关于KMP算法的介绍见：https://blog.csdn.net/v_july_v/article/details/7041827。

      为了便于理解这个next函数，举个简单的例子（牛客网字符串必考题）说明一下：

      题目：在KMP算法中，已知模式串为ADABCADADA,请写出模式串的next数组值？（A）

       A. 0，1，1，2，1，1，2，3，4，3

       B. 0，1，1，1，2，1，2，3，4，3

       C. 2，1，1，2，1，1，2，3，3，4

       D. 1，2，3，2，1，1，2，4，4，3

        next数组值的解法：

          （1）求模式串中，前缀后缀最大的相同长度

                        A  D  A  B  C  A  D  A  D  A

                         0   0  1  0  0  1   2   3  2  3

          （2）将前缀数组后移一位，并将第一位，置-1

                         -1  0  0  1  0  0  1   2  3  2

          （3）将移位后的数组整体+1

                          0  1  1  2  1  1   2  3  4  3

      nextval数组值的解法（或者参考网址：解法）：

          （1）在计算出next值得同时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval就是指向b位的nextval值；

          （2）如果不等，则该a位的nextval值就是它自己a位的next的值。

            上面的nextval数组值为：

                          序号：                1    2   3   4   5   6   7   8   9  10

                          字符串：            A   D   A  B  C   A  D   A  D   A

                          next数组值：     0   1    1   2   1   1   2   3   4   3

                          nextval数组值：0   1    0   2    1   0  1   0   4    0

    C++代码为：

#include <iostream>
#include <vector>

using namespace std;

inline void NEXT(const string &T, vector<int> &next)
{
    //按模式串生成vector,next(T.size())
    next[0] = -1;
    for (int i = 1; i<T.size(); i++) {
        int j = next[i - 1];
        while (T[i] != T[j + 1] && j >= 0)
            j = next[j];//递推计算
        if (T[i] == T[j + 1])
            next[i] = j + 1;
        else
            next[i] = 0;
    }
}

inline string::size_type COUNT_KMP(const string &S, const string &T)
{
    //利用模式串T的next函数求T在主串S中的个数count的KMP算法
    //其中T非空，
    vector<int> next(T.size());
    NEXT(T, next);
    string::size_type index, count = 0;
    for (index = 0; index<S.size(); ++index){
        int pos = 0;
        string::size_type iter = index;
        while (pos<T.size() && iter<S.size()){
            if (S[iter] == T[pos]){
                ++iter;
                ++pos;
            }
            else {
                if (pos == 0)
                    ++iter;
                else
                    pos = next[pos - 1] + 1;
            }
        }//whileend
        if (pos == T.size() && (iter - index) == T.size())
            ++count;
    }//forend
    return count;
}

int main(void)
{
    string S = "abaabcacabaabcacabaabcacabaabcacabaabcac";
    string T = "ab";
    string::size_type count = COUNT_KMP(S, T);
    cout << "模式串T在主串S中出现的次数为："<< count << endl;
    system("pause");
    return 0;
}// 模式串T在主串S中出现的次数为：10

4、实例分析

若使用C++标准库，则添加#include <string>，其主要的函数见文章：C、C++字符串的函数汇总。

# include <iostream>
# include <string>
using namespace std;

int main()
{
    string str = "when i was young, i listen to radio.";
    string::size_type position;

    position = str.find("listen");

    if (position != str.npos) //npos是个很大的数，如果没找到就会返回npos的值给position
    {
        cout << "第一次出现的下标是：" << position << endl;
    }

    //反向查找子串在str中最后出现的位置
    string flag = "to";
    position = str.rfind(flag);
    cout << "str.rfind(flag):" << position << endl;
    getchar();
    return 0;
}

// 20
//27