古典asp网站源码专门做酒店自助餐的网站

古典asp网站源码,专门做酒店自助餐的网站,南京网站流量优化,重庆锅炉网站建设公司系列文章目录 文章目录系列文章目录一、KMP算法简介#xff08;1#xff09;KMP算法的核心思想#xff08;2#xff09;KMP算法的步骤#xff08;3#xff09;KMP 算法的应用场景二、例题一、找出字符串中第一个匹配项的下标二、最短回文串三、总结一、KMP算法简介 KMP1KMP算法的核心思想2KMP算法的步骤3KMP 算法的应用场景二、例题一、找出字符串中第一个匹配项的下标二、最短回文串三、总结一、KMP算法简介KMPKnuth-Morris-Pratt算法是一种高效的字符串搜索字符串匹配算法由 Donald Knuth、Vaughan Pratt 和 James H. Morris 在1977年共同提出。它是一种改进的字符串匹配算法能够在 O(n m) 的时间复杂度内完成匹配任务其中 n 是主串的长度m 是模式串的长度。1KMP算法的核心思想KMP 算法的核心思想是利用已经匹配的部分信息避免从头开始匹配从而提高效率。它通过预处理模式串构建一个称为 “部分匹配表”也称为 “next 数组”的辅助数组用于记录模式串中每个位置之前的最长相等前后缀的长度。2KMP算法的步骤1.构建部分匹配表next 数组初始化一个长度为 m1 的数组 next其中 m 是模式串的长度。遍历模式串对于每个位置 i从 2 开始找到位置 i 之前的最长相等前后缀的长度 j并赋值给 next[i]。如果当前字符与前缀的下一个字符相同则 j否则继续寻找前缀的匹配位置。2.字符串匹配初始化两个指针 i 和 j分别指向主串和模式串的起始位置。遍历主串对于每个位置 i如果 s[i] 等于 p[j]则同时移动 i 和 j。如果 j 等于 m即匹配成功则返回当前位置 i-m主串中匹配的起始位置。如果 s[i] 不等于 p[j]但 j 大于 0则将 j 设置为 next[j]表示利用部分匹配信息跳过一些比较。如果 j 等于 0即没有找到匹配的前缀则将 i 加 1继续匹配。3.返回结果如果在遍历过程中找到匹配则返回匹配的起始位置。如果遍历完整个主串都没有找到匹配则返回 -1。3KMP 算法的应用场景KMP 算法广泛应用于各种字符串搜索和模式匹配的场景如文本编辑器中的查找功能、编译器中的词法分析、生物信息学中的序列匹配等。二、例题一、找出字符串中第一个匹配项的下标1.题目链接找出字符串中第一个匹配项的下标此解法借鉴leetcode该题宫水三叶评论2.KMP解法思路1匹配过程在模拟 KMP 匹配过程之前我们先建立两个概念前缀对于字符串 abcxxxxefg我们称 abc 属于 abcxxxxefg 的某个前缀。后缀对于字符串 abcxxxxefg我们称 efg 属于 abcxxxxefg 的某个后缀。然后我们假设原串为 abeababeabf匹配串为 abeabf我们可以先看看如果不使用 KMP会如何进行匹配不使用 substring 函数的情况下。首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置。首次匹配的「发起点」是第一个字符 a。显然后面的 abeab 都是匹配的两个指针会同时往右移动黑标。在都能匹配上 abeab 的部分「朴素匹配」和「KMP」并无不同。接下来正是「朴素匹配」和「KMP」出现不同的地方先看下「朴素匹配」逻辑将原串的指针移动至本次「发起点」的下一个位置b 字符处匹配串的指针移动至起始位置。尝试匹配发现对不上原串的指针会一直往后移动直到能够与匹配串对上位置。也就是说对于「朴素匹配」而言一旦匹配失败将会将原串指针调整至下一个「发起点」匹配串的指针调整至起始位置然后重新尝试匹配。这也就不难理解为什么「朴素匹配」的复杂度是 O(m∗n) 了。然后我们再看看「KMP 匹配」过程首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在则跳转到「前缀」的下一个位置继续往下匹配跳转到下一匹配位置后尝试匹配发现两个指针的字符对不上并且此时匹配串指针前面不存在相同的「前缀」和「后缀」这时候只能回到匹配串的起始位置重新开始到这里你应该清楚 KMP 为什么相比于朴素解法更快因为 KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配。因为 KMP 的原串指针不会进行回溯没有朴素匹配中回到下一个「发起点」的过程。第一点很直观也很好理解。我们可以把重点放在第二点上原串不回溯至「发起点」意味着什么其实是意味着随着匹配过程的进行原串指针的不断右移我们本质上是在不断地在否决一些「不可能」的方案。当我们的原串指针从 i 位置后移到 j 位置不仅仅代表着「原串」下标范围为 [i,j) 的字符与「匹配串」匹配或者不匹配更是在否决那些以「原串」下标范围为 [i,j) 为「匹配发起点」的子集。3.分析实现到这里就结束了吗要开始动手实现上述匹配过程了吗我们可以先分析一下复杂度。如果严格按照上述解法的话最坏情况下我们需要扫描整个原串复杂度为 O(n)。同时在每一次匹配失败时去检查已匹配部分的相同「前缀」和「后缀」跳转到相应的位置如果不匹配则再检查前面部分是否有相同「前缀」和「后缀」再跳转到相应的位置 … 这部分的复杂度是 O(m2)因此整体的复杂度是 O(n∗m2)而我们的朴素解法是 O(m∗n) 的。说明还有一些性质我们没有利用到。显然扫描完整原串操作这一操作是不可避免的我们可以优化的只能是**「检查已匹配部分的相同前缀和后缀」**这一过程。再进一步我们检查「前缀」和「后缀」的目的其实是**「为了确定匹配串中的下一段开始匹配的位置」**。同时我们发现对于匹配串的任意一个位置而言由该位置发起的下一个匹配点位置其实与原串无关。举个 对于匹配串 abcabd 的字符 d 而言由它发起的下一个匹配点跳转必然是字符 c 的位置。因为字符 d 位置的相同「前缀」和「后缀」字符 ab 的下一位置就是字符 c。可见从匹配串某个位置跳转下一个匹配位置这一过程是与原串无关的我们将这一过程称为找 next 点。显然我们可以预处理出 next 数组数组中每个位置的值就是该下标应该跳转的目标位置 next 点。当我们进行了这一步优化之后复杂度是多少呢预处理 next 数组的复杂度未知匹配过程最多扫描完整个原串复杂度为 O(n)。因此如果我们希望整个 KMP 过程是 O(mn) 的话那么我们需要在 O(m) 的复杂度内预处理出 next数组。所以我们的重点在于如何在 O(m) 复杂度内处理处 next 数组。4.next 数组的构建接下来我们看看 next 数组是如何在 O(m) 的复杂度内被预处理出来的。假设有匹配串 aaabbab我们来看看对应的 next 是如何被构建出来的。这就是整个 next 数组的构建过程时空复杂度均为 O(m)。至此整个 KMP 匹配过程复杂度是 O(mn) 的。5.代码实现在实际编码时通常我会往原串和匹配串头部追加一个空格哨兵。目的是让 j 下标从 0 开始省去 j 从 -1 开始的麻烦。整个过程与上述分析完全一致一些相关的注释我已经写到代码里。// KMP 算法// ss: 原串(string) pp: 匹配串(pattern)publicintstrStr(Stringss,Stringpp){if(pp.isEmpty())return0;// 分别读取原串和匹配串的长度intnss.length(),mpp.length();// 原串和匹配串前面都加空格使其下标从 1 开始ss ss;pp pp;char[]sss.toCharArray();char[]ppp.toCharArray();// 构建 next 数组数组长度为匹配串的长度next 数组是和匹配串相关的int[]nextnewint[m1];// 构造过程 i 2j 0 开始i 小于等于匹配串长度 【构造 i 从 2 开始】for(inti2,j0;im;i){// 匹配不成功的话j next(j)while(j0p[i]!p[j1])jnext[j];// 匹配成功的话先让 jif(p[i]p[j1])j;// 更新 next[i]结束本次循环inext[i]j;}// 匹配过程i 1j 0 开始i 小于等于原串长度 【匹配 i 从 1 开始】for(inti1,j0;in;i){// 匹配不成功 j next(j)while(j0s[i]!p[j1])jnext[j];// 匹配成功的话先让 j结束本次循环后 iif(s[i]p[j1])j;// 整一段匹配成功直接返回下标if(jm)returni-m;}return-1;}二、最短回文串1.题目链接最短回文串2.算法思路使用 KMP 字符串匹配算法来找出这个最长的前缀回文串。反转字符串首先将给定的字符串反转得到其反转字符串。寻找最长回文前缀将原始字符串和它的反转字符串拼接起来在原始字符串后面添加一个特殊字符以区分前后例如 #然后使用 KMP 算法找到这个拼接字符串的最长回文前缀。构造最短回文串根据找到的最长回文前缀可以确定需要添加到原始字符串前面的字符以使其成为回文串。具体来说需要添加的字符是原始字符串中不包含在最长回文前缀中的部分。3.代码示例publicStringshortestPalindrome(Strings){// 如果字符串为空或长度为0直接返回原字符串if(snull||s.isEmpty()){return;}// 反转给定的字符串StringrevnewStringBuilder(s).reverse().toString();// 将原始字符串和它的反转字符串拼接起来并在中间添加一个特殊字符#以区分Stringstrs#rev;// 计算部分匹配表next数组用于KMP算法int[]nextcomputeNextArray(str);// next数组的最后一个元素表示最长回文前缀的长度intlennext[next.length-1];// 构造最短回文串需要添加的字符是原始字符串中不包含在最长回文前缀中的部分returnrev.substring(0,rev.length()-len)s;}/** * 计算部分匹配表next数组用于KMP算法 * param s 字符串 * return next数组 */privateint[]computeNextArray(Strings){intms.length();int[]nextnewint[m];intj0;// 遍历字符串计算next数组for(inti1;im;i){// 当前字符不匹配且j不为0时回溯到前缀的匹配位置while(j0s.charAt(i)!s.charAt(j)){jnext[j-1];}// 如果当前字符匹配继续向右移动if(s.charAt(i)s.charAt(j)){j;}// 记录当前位置的最长匹配前缀长度next[i]j;}returnnext;}三、总结以上就是本文全部内容主要介绍了KMP算法的核心思想与具体的操作步骤并用了两道例题带大家了解KMP在具体算法中的应用KMP算法需要多加练习才可以掌握的更好大家如果在刷题的过程中有遇到的相关问题可以在评论区探讨。感谢各位能够看到最后如有问题欢迎各位大佬在评论区指正希望大家可以有所收获创作不易希望大家多多支持