字符串匹配算法(KMP)

简介: String字符串匹配算法@Date 2017.06.09DEMO代码链接暴力匹配时间复杂度O(m * n) private static int forceMatch(String originS, String matchedS) { char[] originArray = originS.

String字符串匹配算法

@Date 2017.06.09

DEMO代码链接

暴力匹配

  • 时间复杂度O(m * n)
    private static int forceMatch(String originS, String matchedS) {

        char[] originArray = originS.toCharArray();
        char[] matchedArray = matchedS.toCharArray();

        int originLen = originS.length();
        int matchedLen = matchedS.length();

        int i = 0, j = 0;
        while (i < originLen && j < matchedLen) {
            if (originArray[i] == matchedArray[j]) {
                // 相等则继续位移比较(需要同时移位)
                i++;
                j++;
            } else {
                // 不相等则长字符串回到原点,重新比较
                i = i - j + 1;
                j = 0;
            }
        }
        // 匹配字符串完全找到
        if (j == matchedLen) {
            return i - j;
        } else {
            return -1;
        }
    }

KMP匹配

  • 时间复杂度O(m + n)
    /**
     * @param originS  长字符串
     * @param matchedS 要匹配的字符串
     * @return 匹配字符在长字符串中的位置
     */
    private static int kmpMatch(String originS, String matchedS) {
        // next 数组各值的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀。
        // 例如如果next [j] = k,代表j 之前的字符串中有最大长度为k 的相同前缀后缀

        char[] originArray = originS.toCharArray();
        char[] matchedArray = matchedS.toCharArray();

        int originLen = originS.length();
        int matchedLen = matchedS.length();

        int[] next = getNext(matchedArray);

        int i = 0, j = 0;
        while (i < originLen && j < matchedLen) {
            if (j == -1 || originArray[i] == matchedArray[j]) {
                // 相等则继续位移比较(需要同时移位)
                i++;
                j++;
            } else {
                // j != -1,且当前字符匹配失败(originArray[i] != matchedArray[j]),则令 i 不变,j = next[j]
                // next[j]即为j所对应的next值
                // 失配时,模式串向右移动的位数为:已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
                // 失配时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值
                j = next[j];
            }
        }
        // 匹配字符串完全找到
        if (j == matchedLen) {
            return i - j;
        } else {
            return -1;
        }
    }

    /**
     * 获取失配时的位移数组
     * 求解原理为:
     * 1. 匹配字符串的前缀后缀的公共元素的最大长度值的对应数组
     * 2. eg: abab : 0 0 1 2
     * 3. 最大对称长度的前缀后缀,然后整体右移一位,初值赋为-1
     * 4. eg: abab : -1 0 0 1
     * @param matchedArray 需要匹配的pattern字符串
     * @return 位移数组
     */
    private static int[] getNext(char[] matchedArray) {
        int matchedLen = matchedArray.length;
        int[] next = new int[matchedLen];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < matchedLen - 1) {
            // matchedArray[k]表示前缀,matchedArray[j]表示后缀
            // matchedArray[j] == matchedArray[k] 此判断是因为matchedArray[j]已经失配,用相同的matchedArray[k], 位移后去匹配一样是失配.
            // 故二者相等时,继续递归
            if (k == -1 || matchedArray[j] == matchedArray[k]) {
                ++k;
                ++j;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }
相关文章
|
4月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
2月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
90 1
两个字符串匹配出最长公共子序列算法
|
2月前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
20 0
|
2月前
|
算法
KMP算法
KMP算法
34 0
|
4月前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
4月前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
5月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
287 1
|
5月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
127 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
4月前
|
算法
KMP算法
KMP算法
31 0
|
4月前
|
算法 C++
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
87 0