字符串算法-BP产品使用说明书

10.2 字符串算法

字符串处理是编程中常遇到的问题，字符串匹配在数据挖掘和搜索算法中应用广泛。以下介绍三种有效的字符串匹配算法：朴素字符串匹配算法、Rabin-Karp算法和Knuth-Morris-Pratt算法。

字符串匹配是查找字符串T中是否包含字符串P。我们把字符串T称为原字符串，把字符串P称为查找模式。假设T的长度为n，P的长度为m，很明显|m|≤|n|。如果我们在进行字符串匹配的时候存在一个整数s，0≤s≤n-m，使得P字符串在T中被找到，即P[1...m]=T[s+1...s+m]，我们就称s为字符串P匹配查找过程的有效位移。从这个角度来看，字符串匹配的过程其实就是查找在字符串T中模式P出现的所有有效位移。

10.2.1 朴素字符串匹配算法

朴素字符串匹配算法是一种比较原始的字符串匹配算法，它以模式P为单位去比较字符串，循环地遍历字符串T，找出所有的有效位移s。朴素字符串匹配算法思想比较简单，直接来看看代码就能理解了。

#include 
using namespace std;

/****朴素字符串匹配****/
list naiveStringMartch(const string *T, const string P){
    int n = T->size(), m = P.size();
    list res;
    for (int s = 0; s <= n - m; s++) {
        bool flag = true;
        for (int i = 0; i < m>at(s + i) != P[i]) {
                flag = false;
                break;
            }
        }
        if (flag) res.push_back(s);
    }
    return res;
}