差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:王智彪:后缀数组 [2021/07/26 18:52]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:后缀数组 [2021/07/28 15:53] (当前版本)
王智彪
@@ 行 31: / 行 31: @@
 子串在后缀数组里，就是后缀数组的前缀，所以我们可以枚举后缀，然后计算前缀的总数，再减掉重复的。
-前缀总数是子串个数就是 ${\frac n(n+1) 2}$ 。然后按照后缀排序的顺序枚举后缀，每次新增的子串就是除了与上一个后缀的 $lcp$ 之外的其他的前缀一定是新增的， $lcp$ 的部分在上一个后缀已经计算过了。所以答案是 ${\frac n(n+1) 2}-\sum_{i=2}^{n} height[i]$ 。
+前缀总数是子串个数就是 ${\frac {n(n+1)} 2}$ 。然后按照后缀排序的顺序枚举后缀，每次新增的子串就是除了与上一个后缀的 $lcp$ 之外的其他的前缀一定是新增的， $lcp$ 的部分在上一个后缀已经计算过了。所以答案是 ${\frac {n(n+1)} 2}-\sum_{i=2}^{n} height[i]$ 。
 如果有一个让求出现了 $k$ 次的子串，就求出 $height$ 数组，如果相邻的 $k-1$ 个位置的值的最小值大于 $0$ ，就说明有字符串，如果求其中的最大长度，就求所有 $k-1$ 个相邻位置的 $height$ 值的最小值，再在其中取最大值。
@@ 行 316: / 行 316: @@
 </hidden>
+.求最长回文子串
+注意最长回文子串可以是奇数长度也可以是偶数长度。比如最长回文子串是 $aabaa$ ，也就是奇数的情况，整个串是 $hijaabaaxy$ ，这种已经很自然地在中间放一个 $z+1$ 的字符，然后倒序抄过来，变成 $hijaabaaxy\{xyaabaajih$ ，只需要看 $baaxy…$ 和 $baajih$ 的 $lcp$ 就可以了。也就是沿着同一个点向两边看 $lcp$ ，这样的长度是 $2×lcp-1$ ，因为有一个公共点重复了。同理如果对于可能的偶数情况，最长回文子串是 $aabbaa$ ，整个串是 $hijaabbaaxy$ ，倒过来变成 $hijaabbaaxy\{xyaabbaajih$ 。只需要看 $baaxy…$ 和 $baajih$ 的 $lcp$ 即可。这个直接把结果乘二就行了，最后比较出所有的最大值就是答案。
+<hidden 代码>
+<code cpp>
+void prework() {
+	for(int i=1; i<=n; i++) best[i][0]=height[i];
+	for(int j=1; (1<<j)<n; j++)
+		for(int i=1; i+(1<<j)-1<=n; i++)
+			best[i][j]=min(best[i][j-1],best[i+(1<<(j-1))][j-1]);
+}
+inline int query(int l,int r) {
+	int k=log2(r-l+1);
+	return min(best[l][k],best[r-(1<<k)+1][k]);
+}
+//st表，区间min
+inline int lcp(int l,int r) {
+	if(l>r) swap(l,r);
+	return query(l+1,r);
+}
+int main() {
+	scanf("%s",s+1);
+	n=strlen(s+1);
+	s[n+1]='z'+1;
+	m='z'+2;
+	for(int i=1; i<=n; i++) {
+		s[i+n+1]=s[n-i+1];
+	}
+	printf("%s\n",s+1);
+	n=n*2+1;
+	get_SA();
+	get_height();
+	prework();
+	n>>=1;
+	int maxv=0;
+	for(int i=1; i<=n; i++) {
+		int v=lcp(rk[i],rk[2*n+3-i]);
+		if(2*v>maxv) {
+			maxv=2*v;
+			//printf("  %d %d\n",i,2*n+3-i);
+			//printf("  %d\n",v);
+		}
+		v=lcp(rk[i],rk[2*n+2-i]);
+		if(2*v-1>maxv) {
+			maxv=2*v-1;
+			//printf(" %d %d\n",i,2*n+2-i);
+			//printf(" %d\n",v);
+		}
+	}
+	printf("%d\n",maxv);
+	return 0;
+}
+</code>
+</hidden>
+.后缀数组还可以解决连续重复子串的问题
+我们规定连续重复串为：某一个字符串 $L$ 是由某个字符串 $S$ 重复 $R$ 次得到的，则称 $L$ 是一个连续重复串， $R$ 是这个字符串的重复次数。
+.1求连续重复子串出现次数最大值
+首先肯定要枚举长度 $k$ ，判断 $k$ 是否整除总长度，然后只需要比较 $lcp(rk[1],rk[k+1])$ 是否是 $n-k$ 就可以了。因为前提是整除，然后 $lcp(rk[1],rk[k+1])$ 是下标为 $1$ 的串和下标为 $k+1$ 的串的相同前缀，如果把 $k+1$ 的剩下都包括了就可以说明每 $k$ 个都一样，画个图就知道了。于是还需要枚举最小的长度就可以了，求出 $height$ 之后复杂度是 $O(n)$ 的。
+.2求一个字符串的所有子串中重复次数最多的连续重复子串
+先穷举长度 $L$ ，然后看所有的长度为 $L$ 的子串最多能连续出现几次。出现一次就是这个串本身，我们直接考虑两次及以上的情况，注意如果子串出现了至少两次，我们取这些字符 $s[1],s[L+1],s[2*L+1]…$ ，这些字符中一定会有两个出现在这个大串中，其实我们只需要将这些字符代表的相邻后缀取一下 $lcp$ 就行，比如现在有一个串是 $habcabcabcabxyz$ ，然后这个最大显然是 $cabcabcabxyz$ 和 $cabcabxyz$ ，这个的 $lcp$ 长度是 $6$ ，然后查一下实际上是 $3$ 个，也就是 ${\frac 6 3}+1$ 。但是这并不一定正确，因为比如现在串删了一个字符，变成了 $habcabcabcaxyz$ 。现在长度为 $5$ ，但事实上还是应该是 $3$ ，原因很简单，我们并没有将所有的情况都讨论进去，只是每隔这个长度找一下，导致有的串被切成两个段了，次数会少算 $1$ ，这个很直观地可以看出来可以向前移动 $5\%3=2$ 的长度，因为这些长度相当于被浪费了，然后算一下那两个新的点的 $lcp$ ，如果大于等于 $L$ ，说明刚才有一个没算进去，反之不用管，这样复杂度就是 $O(n×({\frac 1 1}+{\frac 1 2}+…+{\frac 1 n}))=O(nlogn)$ 。
+.出现或反转后出现在每个字符串中的最长子串
+我们将所有字符串和他们倒过来的字符串用没出现过的字符分割并相连。然后把除了分隔符之外的每一个位置都标记好是哪个字符串中出现的。然后显然是二分答案。翻转后的字符串和翻转之前的字符串都是标记同一个字符串，一起求后缀数组，这样就可以既考虑翻转又考虑没翻转的情况了。
+<hidden 代码>
+<code cpp>
+bool check( int limit , int len ) {
+	memset( have , false , sizeof(have) ) ;//清空，防止受上次结果影响
+	if( in[sa[1]] ) {//因为height数组比较的是sa[i-1]和sa[i] 所以这里先把1的放进去
+		have[in[sa[1]]] = true ;//因为长度必然比limit大，所以一定是true
+	}
+	for( int i = 2 ; i <= len ; i ++ ) {
+		if( height[i] < limit ) {
+			int cnt = 0 ;
+			for( int j = 1 ; j <= n ; j ++ ) {
+				if( have[j] ) cnt ++ ;
+			}
+			if( cnt == n ) return true ;
+			memset( have , false , sizeof(have) ) ;//一定要把所有的清空
+		}
+		if( in[sa[i]] ) {
+			have[in[sa[i]]] = true ;//和上面同理
+		}
+	}
+	int cnt = 0 ;
+	for( int j = 1 ; j <= n ; j ++ ) {
+		if( have[j] ) cnt ++ ;
+	}
+	return cnt == n ;//别忘了有可能最后一步才凑够，这里要重新判断一下
+}
+        //main函数中
+	for( int i = 1 ; i <= n;  i ++ ) {
+		scanf( "%s" , str ) ;
+		int l = strlen( str ) ;
+		mm = min( mm , l ) ;
+		for( int j = 0 ; j < l ; j ++ ) {//顺着存
+			r[len] = str[j] ;
+			in[len++] = i ;
+		}
+		r[len++] = 'z' + i ;//这里一定要区别开
+		for( int j = l - 1 ; j >= 0 ; j -- ) {//倒着存
+			r[len] = str[j] ;
+			in[len++] = i ;
+		}
+		r[len++] = 'z' + i + n ;//这里一定要区别开
+	}
+</code>
+</hidden>
+剩下的oi-wiki上的题单待补，先爬去看别的了。

CVBB ACM Team

用户工具

站点工具

差别

页面工具