串的模式匹配(查找子串在主串中的位置).cpp

串的模式匹配问题算法cpp源代码

// 串的模式匹配(查找子串在主串中的位置)


#include <iostream>
#include <cstring>

using namespace std;

// 一般方法：从主串和模式串的第一个字符开始比较，若相等，则继续比较后续字符；
// 否则从主串的下一个字符起再重新和模式字符比较。 
int normalMatch(const string& s1, const string& sub)
{
    int n1 = s1.length();
    int nsub = sub.length();
    int i = 1, j = 1; // i 指向 s1, j 指向 sub
    while(i <= n1 && j <= nsub)
    {
        if(s1[i-1] == sub[j-1]) // continue to compare the next charicter
        {
            ++i;
            ++j;
        }
        else // 指针后退，重新开始匹配 
        {
            i = i - j + 2;
            j = 1;
        }
    }
    if(j > nsub) // 匹配成功 
        return i - nsub;
    else  // 匹配失败 
        return 0;
} 

// KMP 方法：每当一趟匹配过程中出现字符匹配不等时，不回溯主串的指针，而是利用
// 已经得到的“部分匹配结果”将模式串向右“滑动”尽可能远的一段距离后，继续比较
int KMPMatch(const string& s1, const string& sub)
{
    int n1 = s1.length();
    int nsub = sub.length();
    int i = 1, j = 0;
    
    // 求模式串的 next[] 
    int* const next = new int[nsub+1];
    next[1] = 0;
    while(i < nsub)
    {
        if(j == 0 || s1[i-1] == s1[j-1])
        {
            ++i;
            ++j;
            if(s1[i-1] != s1[j-1])
                next[i] = j;
            else
                next[i] = next[j];
        }
        else
            j = next[j];
    }
    
    // 匹配 
    i = 1;
    j = 1;
    while(i <= n1 && j <= nsub)
    { 
        if(j == 0 || s1[i-1] == sub[j-1])
        {
            ++i;
            ++j;
        }
        else
            j = next[j]; // 模式串向右滑动 
    }
    delete []next;
    if(j > nsub)
        return i - nsub;
    else
        return 0;
}

int main()
{
    string s1("this is the test of string matching.");
    string sub("test");
    cout << "normal matching: " << normalMatch(s1, sub) << endl;
    cout << "KMP matching: " << KMPMatch(s1, sub) << endl;
    system("pause");
    return 0;
}