怎样在c++中实现自定义的字符串匹配规则

在 C++ 中实现自定义的字符串匹配规则，你可以使用以下几种方法：

暴力匹配（Brute Force）

遍历目标字符串，逐个字符与模式字符串进行比较。这种方法的时间复杂度较高，为 O(n*m)，其中 n 和 m 分别为目标字符串和模式字符串的长度。

#include <iostream>
#include <string>

bool isMatch(const std::string& target, const std::string& pattern) {
    int n = target.size();
    int m = pattern.size();

    for (int i = 0; i <= n - m; ++i) {
        bool match = true;
        for (int j = 0; j < m; ++j) {
            if (target[i + j] != pattern[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            return true;
        }
    }
    return false;
}

int main() {
    std::string target = "hello";
    std::string pattern = "ll";
    std::cout << (isMatch(target, pattern) ? "匹配成功" : "匹配失败") << std::endl;
    return 0;
}

KMP 算法（Knuth-Morris-Pratt）

KMP 算法是一种高效的字符串匹配算法，时间复杂度为 O(n+m)。它通过预处理模式字符串，避免在不匹配时重新检查已匹配的字符。

#include <iostream>
#include <string>

std::vector<int> computePrefixFunction(const std::string& pattern) {
    int m = pattern.size();
    std::vector<int> pi(m, 0);
    int k = 0;

    for (int q = 1; q < m; ++q) {
        while (k > 0 && pattern[k] != pattern[q]) {
            k = pi[k - 1];
        }
        if (pattern[k] == pattern[q]) {
            ++k;
        }
        pi[q] = k;
    }
    return pi;
}

bool isMatch(const std::string& target, const std::string& pattern) {
    int n = target.size();
    int m = pattern.size();
    std::vector<int> pi = computePrefixFunction(pattern);

    int q = 0;
    for (int i = 0; i < n; ++i) {
        while (q > 0 && pattern[q] != target[i]) {
            q = pi[q - 1];
        }
        if (pattern[q] == target[i]) {
            ++q;
        }
        if (q == m) {
            return true;
        }
    }
    return false;
}

int main() {
    std::string target = "hello";
    std::string pattern = "ll";
    std::cout << (isMatch(target, pattern) ? "匹配成功" : "匹配失败") << std::endl;
    return 0;
}

BM 算法（Boyer-Moore）

BM 算法是一种快速的字符串匹配算法，平均时间复杂度为 O(n+m)。它通过跳过一些不匹配的字符来减少匹配次数。

#include <iostream>
#include <string>

std::string badCharacterTable(const std::string& pattern) {
    int m = pattern.size();
    std::string badCharTable(m, 0);

    for (int i = 0; i < m; ++i) {
        badCharTable[pattern[i]] = i;
    }
    return badCharTable;
}

std::string goodSuffixTable(const std::string& pattern, const std::string& badCharTable) {
    int m = pattern.size();
    std::string goodSuffixTable(m, 0);
    int k = 0;

    for (int i = m - 1; i >= 0; --i) {
        while (k > 0 && pattern[k] != pattern[i]) {
            k = badCharTable[pattern[k]];
        }
        if (pattern[k] == pattern[i]) {
            ++k;
        }
        goodSuffixTable[i] = k;
    }
    return goodSuffixTable;
}

bool isMatch(const std::string& target, const std::string& pattern) {
    int n = target.size();
    int m = pattern.size();
    std::string badCharTable = badCharacterTable(pattern);
    std::string goodSuffixTable = goodSuffixTable(pattern, badCharTable);

    int i = 0;
    int j = 0;
    while (i < n) {
        if (j > 0 && pattern[j] != target[i]) {
            j = goodSuffixTable[j - 1];
        }
        if (pattern[j] == target[i]) {
            ++i;
            ++j;
        } else if (j == 0) {
            ++i;
        } else {
            j = badCharTable[pattern[j]];
        }
    }
    return j == m;
}

int main() {
    std::string target = "hello";
    std::string pattern = "ll";
    std::cout << (isMatch(target, pattern) ? "匹配成功" : "匹配失败") << std::endl;
    return 0;
}

这些方法可以实现自定义的字符串匹配规则。你可以根据自己的需求选择合适的方法。

最新问答

相关标签