网站建设 客户,群晖wordpress 外网,网站模板代码,做民宿的有哪些网站Z算法#xff08;扩展KMP#xff09; 文章目录 Z算法#xff08;扩展KMP#xff09;朴素求法线性求法力扣类型题变种题#xff1a;[3303. 第一个几乎相等子字符串的下标](https://leetcode.cn/problems/find-the-occurrence-of-first-almost-equal-substring/) 所谓Z算法扩展KMP 文章目录 Z算法扩展KMP朴素求法线性求法力扣类型题变种题[3303. 第一个几乎相等子字符串的下标](https://leetcode.cn/problems/find-the-occurrence-of-first-almost-equal-substring/) 所谓Z算法就是求一个字符串中每个后缀子串和主串的前缀匹配字符数的数组其也成为Z数组 eg主串为aaaab(首位总为0因为包含首位即本体无意义) aaaab aaab - 3aaaab aab - 2aaaab ab - 1aaaab b - 0结果集[0, 3, 2, 1,0] 朴素求法
时间复杂度为O(n^2)暴力获取Z数组。
每次都从头匹配如果符合往后不符合则返回下一次又从头匹配。
vectorint z_function_trivial_simple(string s)
{int n (int)s.length();vectorint z(n);for (int i 1; i n; i){while (i z[i] n s[z[i]] s[i z[i]])z[i];}return z;
}线性求法 我们使用一个滑动窗口[l,r]这个滑动窗口总是往右移动我们可以称之为Z_box
这个z_box具有特性s[l, r] s[0, r-l]s为字符串l和r总是从0开始 我们再次复习一下z数组的含义z[i]表示从s[i]开始直到末尾的子字符串和s整个字符串匹配的前缀和 问题一如何获取这个滑动窗口
由于滑动窗口z_box总是向右移动所以我们要用z数组及i来辅助获取。
具体方法为当iz[i] -1 r时修改l和r的位置是l i , r i z[i] - 1
原因1. 我们希望滑动窗口会比需要匹配的数字更靠后或者说能够包含未来匹配的位置并且滑动窗口总是往右的。
i这里代表新窗口的起始位z[i]代表匹配的长度 -1 是因为z[i]的数字里包含i的位置。
换句话说所谓新的z_box就是更往右的匹配上的子串前缀。这么说可能比较抽象请以下图例辅助理解 问题二这个滑动窗口的具体作用
这个滑动窗口只在i ∈[l, r]时发生作用。
我们以上图例作为一个例子作为讲解 此时 i 5 5包含在[4,6]中而且刚好是中间 因为 s[0,2] s[4,6] 那么z[5] 可以直接参考z[1]获取 即z[i] z[i - l] 但这只是上图的可能性因为上图中z[i-l] 1 这个值小于r - i 1 - 6- 5 1 - 2我们已经知道了最多只能匹配到这里
但是还有一种可能就是z[i-1] (r - i 1)这种情况我们无法预测r后面是否可以继续匹配那么我就需要从r的后一位开始匹配。而这种匹配方式则回到了原始的匹配中不再进行讲解但是这种情况我们依然可以省略已经处于滑动窗口中的匹配。
下面代码展示如果还不理解可以用这个网站模拟演示Z函数 C 代码 vectorint z_function(string s)
{ vectorint z(s.size(), 0);int l 0, r 0;for (int i 1; i s.size(); i){if (i r z[i - l] r - i 1){z[i] z[i - l];}else {z[i] max(0, r - i 1);// 从头开始暴力求解while (i z[i] s.size() s[z[i]] s[i z[i]])z[i];}if (i z[i] - 1 r){l i, r i z[i] - 1;}// 可以打印进行看看cout i: i , z[i]: z[i] , [l, r]: [ l , r]endl;}return z;
}Python代码 def getZArray(self, s : str) - List[int]:# z[i] 为从i开始能和主串从头匹配的字符总数z [0] * len(s)l, r 0, 0for i in range(1, len(s)):# 当i在窗口内# 如果z[i-l] (r-i1)说明z[i-l]能匹配的字符数已经可知直接获取# 否则有可能超出这个数字需要从末尾继续暴力寻找if i r: # i在窗口内z[i] min(z[i - l], r - i 1)while i z[i] len(s) and s[z[i]] s[i z[i]]: # 暴力匹配剩余部分z[i] 1if i z[i] - 1 r: # 更新窗口边界l, r i, i z[i] - 1return z力扣类型题
变种题3303. 第一个几乎相等子字符串的下标
这道题在Z算法的基础上变形为前缀后缀的组合详情可以看这篇题解写得很好我不班门弄斧了。贴上我的代码。 C class Solution {
public:int minStartingIndex(string s, string pattern) {int m pattern.size(), n s.size();string combine pattern s;reverse(pattern.begin(), pattern.end());reverse(s.begin(), s.end());string combinervs pattern s;vectorint pre getZArray(combine); // pre_l z[ml]vectorint suf getZArray(combinervs); // suf_r z[m(n-r-1)]for (int l 0, r m - 1; r n; l, r){if (pre[m l] suf[m (n - r - 1)] 1 m)return l;}return -1;}private:vectorint getZArray(string s){vectorint z(s.size(), 0);int l 0, r 0;for (int i 1; i s.size(); i){if (i r z[i - l] r - i 1){z[i] z[i - l];}else {z[i] max(0, r - i 1);while (i z[i] s.size() s[z[i]] s[i z[i]])z[i];}if (i z[i] - 1 r){l i, r i z[i] - 1;}}return z;}
};Python from typing import Listclass Solution:def getZArray(self, s: str) - List[int]:# z[i] 是从索引 i 开始的子串与主串前缀匹配的长度z [0] * len(s)l, r 0, 0for i in range(1, len(s)):if i r: # i在窗口内z[i] min(z[i - l], r - i 1)while i z[i] len(s) and s[z[i]] s[i z[i]]: # 暴力匹配剩余部分z[i] 1if i z[i] - 1 r: # 更新窗口边界l, r i, i z[i] - 1return zdef minStartingIndex(self, s: str, pattern: str) - int:m, n len(pattern), len(s)# 生成前缀和后缀Z数组combined pattern sreversed_combined pattern[::-1] s[::-1]pre self.getZArray(combined)suf self.getZArray(reversed_combined)# 检查匹配位置for l in range(n - m 1):r l m - 1if pre[m l] suf[m (n - r - 1)] 1 m:return lreturn -1参考
[1] Z函数扩展KMP
[2] 3303 第一个几乎相等子字符串的下标——题解
