做涉黄的视频网站用什么服务器,opencart 构建电子商务网站,上海婚恋网站排名,企业形象设计包括哪些假设给定一个s长度为的n字符串。那么这个字符串的 z-function #xff08;“zet-function”#xff09;是一个长度为 的数组#xff0c;其中的 -th 元素等于最大字符数#xff0c;从 position i开始#xff0c;i与字符串的第一个字符n重合。
换句话说#xff0c;z[i]它是…假设给定一个s长度为的n字符串。那么这个字符串的 z-function “zet-function”是一个长度为 的数组其中的 -th 元素等于最大字符数从 position i开始i与字符串的第一个字符n重合。
换句话说z[i]它是s字符串及其i-th 后缀的最大通用前缀。
注意在本文中为了避免歧义我们将字符串视为0索引即字符串的第一个字符具有索引0最后一个n-1字符是。
z 函数的第一个元素通常z[0]被认为等于零。
本文描述了一种计算z函数的O (n算法以及该算法的各种应用。
例子
下面是针对多个计算的 z 函数的示例
aaaaa
z[0] 0
z[1] 4
z[2] 3
z[3] 2
z[4] 1。aaabaaab
z[0] 0
z[1] 2
z[2] 1
z[3] 0
z[4] 2
z[5] 1
z[6] 0。abacbaa
z[0] 0
z[1] 0
z[2] 1
z[3] 0
z[4] 3
z[5] 0
z[6] 1。朴素算法
以下算法基本实现时间复杂度O n^2 public static int[] zFunction(String s){int ns.length();char[]sas.toCharArray();int[] znew int[n];for(int i1;in;i){while(iz[i]nsa[z[i]]sa[iz[i]]){z[i];}}return z;}对于每个位置i我们只需从零开始迭代它的z[i]答案直到我们发现不匹配或到达线的末尾。
计算 z 函数的有效算法
为了获得有效的算法我们将逐个计算值从i1到同时在计算下一个值时我们将尝试n-1充分利用已经计算出的值z[i]。
为简洁起见s我们将与字符串前缀匹配的子字符串称为匹配栏。例如您要查找的z函数z[i]的值是从position开始并将在positioni,iz[i]-1结束的最长匹配段。
为此我们将保持重合最[左;r]右边段的坐标即我们将存储在所有检测到的段的右侧结束的坐标。从某种意义上说索引r是算法已经扫描了我们的字符串的边界其他一切都还不知道。
然后如果我们要计算z函数的下一个值的当前索引是i我们有以下两个选项之一 ir—换句话说目前的情况超出了我们已经处理的情况。 然后我们将使用一个简单的算法进行搜索z[i]即只尝试、等的值z[i]0。请注意最后如果z[i]结果是z[i]1那么我们将不得不更新最右边段[左;r]的坐标——因为它iz[i]-1保证0大r于。 i≤r—即当前位置位于重合段[左;r]内。 在这种情况下我们可以使用已经计算出的z函数的先前值来初始化值而不是用零而是用一些可能更高的数字来初始化值z[i]。
为此请注意子字符串s[l…r]重合s[0…r-l]。这意味着作为初始近似值z[i]我们可以从直线中获取相应的值即s[0…r-l]值z[i-l]。
但是该值z[i-l]可能太大以至于当应用于某个位置我时它会“爬出”边界r。这是不允许的因为我们对右边的符号一无所知而且它们可能与所需的符号r不同。
让我们举一个这种情况的例子使用以下行作为示例
aaaabaa当我们到达最后一个位置i6时当前最右边的行是[5:6]。考虑到此段该位置将对应6,6-51于答案等于z[1]3的位置。显然你不能用这样的值初始化z[6]这是完全不正确的。我们可以初始化的最大值是因为它是1不超过[左;r]行的最大值。
因此仅z[i]采用以下表达式作为初始近似值是安全的
z_0[i]min(r-i1z[i-l])。
使用z[i]这样的值初始化后我们再次使用一个简单的算法因为在边界之后一般来说可以找到z_0[i]线段的延续r这是我们无法仅用z函数的先前值来预测的巧合。
因此整个算法由两种情况组成实际上仅在初始值上有所不同在第一种情况下假设它等于零在第二种情况下它由根据z[i]指定公式的先前值确定。之后算法的两个分支都简化为执行一个从指定的初始值立即开始的简单算法。
事实证明该算法非常简单。尽管他们每个人都我以一种或另一种方式执行一个微不足道的算法但我们通过获得一种在线性时间内工作的算法取得了重大进展。为什么会这样在我们介绍算法的实现之后我们将在下面考虑。
实现 public static int[] zFunction(String s){int ns.length();char[]sas.toCharArray();int[] znew int[n];int left0,right0;for(int i1;in;i){if (iright){z[i]Math.min(right-i1,z[i-left]);}while(iz[i]nsa[z[i]]sa[iz[i]]){z[i];}if (iz[i]-1right){lefti;rightiz[i]-1;}}return z;}数组最初填充为z为0。假设当前最右边的重合部分等于[0;0]即一个故意的小部分其中不会落i下
在循环中我们首先使用上述算法来确定初始值z[i]——它要么保持为零要么根据给定的i1…n-1公式计算。
之后执行一个简单的算法试图尽可能地增加该值z[i]。
最后如果需要[左;r]此更新则更新匹配的当前最右边部分即ifiz[i]-1r
