字符串查找算法

今天我来介绍2个比较常用的字符串查找算法,它们分别是“BF算法(Brute Force)”和“KMP算法”。虽然这两个算法都不是效率最高的,但是它们却是最基础的和改进的。

BF算法 是最普通的字符串查找算法,这个算法虽然编写效率高,但是执行效率超低。因为BF算法的思想是用模式串(需要查找的字符串)第一个字符匹配目标串(被查找的字符串)第一个字符,如果相同则将模式串第二个字符匹配目标串第二个字符。如果第一个字符不相同,就将模式串目标串后移一位,拿目标串第二个字符模式串第一个字符比较,如此类推。这样的思想是不好的,因为会做很多愚蠢的无用功动作,下面的 KMP算法 就能很好地改善这样的行为。

KMP算法 是从 BF算法 改进过来的,它把匹配失败的信息记录下来,并且做成一个可以减少匹配次数的数组。这个数组叫做“Next数组”,这样的做法是为了改良 BF算法 的硬伤:模式串第一个字符目标串不相同则将模式串后移一位,这样会丢弃掉前面所有匹配失败的信息。所以就用 Next数组 把匹配失败的信息都记录下来。如果在哪失配了,就通过 Next数组 的指向并进行下一轮的匹配

Next数组 的主要实现原理:

[如何正确地阅读以下内容]

请先从上到下阅读绿色的分隔线左边的内容,然后再通过分隔线右边的内容与分隔线左边的图片进行阅读。蓝色的圆框标注的是顺序步骤。

BF算法 与 KMP算法 的实现代码:

#include <iostream>

using namespace std;

void KMP(char *String, char *Key);
void KMPGetNext(char *String, int *&Next);
void BF(char *String, char *Key);

int main(){
    char *String = "ababcf0g";
    char *Key = "abc";

    BF(String, Key);
    KMP(String, Key);

    system("pause");
    return 0;
}

void BF(char *String, char *Key){
    int i, j, SLen = strlen(String), KLen = strlen(Key);
    i = j = 0;

    while(i < SLen && j < KLen){
        if(String[i] == Key[j]){
            i++;
            j++;
        }else{
            i = i - j + 1;
            j = 0;
        }
    }

    if(j == KLen){
        cout << i - KLen << endl;
    }else{
        cout << -1 << endl;
    }
}

void KMP(char *String, char *Key){
    int i = 0, j = 0, SLen = strlen(String), KLen = strlen(Key), *Next = new int[SLen]();

    KMPGetNext(String, Next);   //获取Next数组

    while(i < SLen && j < KLen){
        if(j == -1 || String[i] == Key[j]){
            i++;
            j++;
        }else{
            j = Next[j];    //回溯
        }
    }

    if(j == KLen){
        cout << i - KLen << endl;
    }else{
        cout << -1 << endl;
    }
}

void KMPGetNext(char *String, int *&Next){
    int i = -1, j = 0, SLen = strlen(String);
    Next[0] = -1;

    while(j < SLen){
        if(i == -1 || String[i] == String[j]){
            i++;
            j++;

            *(Next + j) = i;    //在Next数组 后缀+1 的位置放入 前缀+1 的值

        }else{
            i = *(Next + i);    //回溯
        }
    }
}

[温馨提示]

我写的这个 KMP算法 的范例为了让读者更容易理解,并没有进行优化!

标签:计算机, 程序, 设计, 常用, 算法, 字符串, 查找

该文章由 Shiqi Qiu 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源:http://blog.fdawn.com/CPP/22.html

添加新评论