KMP算法字符串匹配

简介:

对于暴力搜索法,当搜索词对应的字符与字符串中的字符不匹配时。将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。

应用KMP算法之后,则有:
= 
KMP算法
“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。

KMP算法实现代码如下

void prefixFun(char *pattern, int *preFun)
{
    int len = 0; //length of pattern
    while ('\0' != pattern[len])
        len++;

    int LOLP = 0; //length of longest prefix
    preFun[1] = 0;
    for (int NOCM = 2; NOCM <= len; NOCM++) //NOCM : number of characters matched
    {
        while (LOLP > 0 && pattern[LOLP] != pattern[NOCM-1])
            LOLP = preFun[LOLP];
        if (pattern[LOLP] == pattern[NOCM-1])
            LOLP++;
        preFun[NOCM] = LOLP;
    }
}

void KMPstrMatching(char *target, char *pattern)
{
    int tarLen = 0;
    int patLen = 0;
    while ('\0' != target[tarLen])
        tarLen++;
    while ('\0' != pattern[patLen])
        patLen++;

    int *preFun = new int[patLen+1];
    prefixFun(pattern, preFun);

    int NOCM = 0; // number of characters matched

    for (int i = 0; i < tarLen; i++)
    {
        while (NOCM > 0 && pattern[NOCM] != target[i])
            NOCM = preFun[NOCM];
        if (pattern[NOCM] == target[i])
            NOCM++;

        if (NOCM == patLen)
        {
            cout<<"Pattern occurs with shift "<<i - patLen + 1<<endl;
            NOCM = preFun[NOCM];
        }
    }

    delete [] preFun;
}
AI 代码解读


转自:http://blog.csdn.net/foreverling/article/details/44730669

目录
打赏
0
0
0
0
248
分享
相关文章
|
8月前
|
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
6月前
|
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
153 1
两个字符串匹配出最长公共子序列算法
|
6月前
|
第四章 KMP算法理论基础
第四章 KMP算法理论基础
63 0
|
6月前
|
KMP算法
KMP算法
63 0
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
8月前
|
KMP算法
KMP算法
58 0
|
8月前
|
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
155 0
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
本程序基于免疫算法实现物流仓储点选址优化,并通过MATLAB 2022A仿真展示结果。核心代码包括收敛曲线绘制、最优派送路线规划及可视化。算法模拟生物免疫系统,通过多样性生成、亲和力评价、选择、克隆、变异和抑制机制,高效搜索最优解。解决了物流仓储点选址这一复杂多目标优化问题,显著提升物流效率与服务质量。附完整无水印运行结果图示。
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
基于GA遗传优化TCN时间卷积神经网络时间序列预测算法matlab仿真
本内容介绍了一种基于遗传算法优化的时间卷积神经网络(TCN)用于时间序列预测的方法。算法运行于 Matlab2022a,完整程序无水印,附带核心代码、中文注释及操作视频。TCN通过因果卷积层与残差连接学习时间序列复杂特征,但其性能依赖超参数设置。遗传算法通过对种群迭代优化,确定最佳超参数组合,提升预测精度。此方法适用于金融、气象等领域,实现更准确可靠的未来趋势预测。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等