后缀数组

题目链接 题意：把一个长度为 n 的只由数字构成的串分成 k 个不为空的子串，使得最大的串最小（大小是指串所对应的十进制数的大小）。 思路：由于长度为 x 的串肯定大于长度为 x-1 的串，因此很容易想到，我们要尽可能使得 k 组串的长度平均（避免出现某一个串的长度非常大的情况）。

题目链接 题意：定义一个函数 F。 For example: F(babbabbababbab, babb) = 6. The list of pairs is as follows: (1, 4), (4, 7), (9, 12) Its continuous sequences are: (1, 4) (4, 7) (9, 12) (1, 4), (4, 7) (4, 7), (9, 12) (1, 4), (4, 7), (9, 12) 二分。 题目描述得很烂，看例子吧，大概就是：如果字符串 y 在字符串 x 中出现 n 次，那么 F(x,y)=n*(n+1)/2

poj 2406 题意：给定一个字符串 L，已知这个字符串是由某个字符串 S 重复 R 次而得到的， 求 R 的最大值 思路：论文题。 转载论文中的题解： 做法比较简单，穷举字符串 S 的长度 k，然后判断是否满足。判断的时候， 先看字符串 L 的长度能否被 k 整除，再看 suffix(1) 和 suffix(k+1) 的最长公共前缀是否等于 n-k。在询问最长公共前缀的时候，suffix(1) 是固定的，所以 RMQ 问题没有必要做所有的预处理，只需求出 height 数组中的每一个数到 height[rank[1]] 之间的最小值即可。整个做法的时间复杂度为 O(n)

题目连接 题意：求所有不同的子串个数。 思路：后缀数组。和上一道题一样，就是数据范围变成了 5E4…1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月02日 星期二 18时32分28秒 4File Name :code/spoj/subst1.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=5E4+7; 32char s[N]; 33int sa[N],rk[N],t[N],t2[N],cnt[N],height[N]; 34int cmp (int *r,int a,int b,int l){ return r[a]==r[b]&&r[a+l]==r[b+l];} 35void getSa(int n,int m) 36{ 37 int *x=t,*y=t2; 38 ms(cnt,0); 39 for ( int i = 0 ; i < n ; i++) cnt[x[i]=s[i]]++; 40 for ( int i = 0 ; i < m ; i++) cnt[i]+=cnt[i-1]; 41 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i; 42 for ( int k = 1 ; k <= n ; k<<=1) 43 { 44 int p = 0; 45 for ( int i = n-k ; i < n ; i++) y[p++] = i; 46 for ( int i = 0 ; i < n; i++) if (sa[i]>=k) y[p++] = sa[i]-k; 47 ms(cnt,0); 48 for ( int i = 0 ; i <n ; i++) cnt[x[y[i]]]++; 49 for ( int i = 0 ;i < m ; i++) cnt[i]+=cnt[i-1]; 50 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i]; 51 swap(x,y); 52 p = 1; 53 x[sa[0]] = 0; 54 for ( int i = 1 ; i < n ; i++ ) 55 x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++; 56 if (p>=n) break; 57 m = p; 58 } 59} 60void getHeight( int n) 61{ 62 int k = 0 ; 63 for ( int i = 0 ; i <n ; i ++) rk[sa[i]] = i ; 64 height[0] = 0 ; 65 for ( int i = 0 ; i < n ; i++) 66 { 67 if (rk[i]==0) continue; 68 if (k) k--; 69 int j = sa[rk[i]-1]; 70 while (s[i+k]==s[j+k]) k++; 71 height[rk[i]] = k; 72 } 73} 74int getSuffix(char s[]) 75{ 76 int len = strlen(s); 77 int up = 0 ; 78 for ( int i = 0 ; i < len ; i++) 79 { 80 int val = s[i]; 81 up = max(up,val); 82 } 83 s[len++]='$'; 84 getSa(len,up+1); 85 getHeight(len); 86 return len; 87} 88int solve ( int n) 89{ 90 ms(cnt,0); 91 int up = 0; 92 for ( int i = 0 ;i <n ; i ++) cnt[height[i]]++, up = max(up,height[i]); 93 for ( int i = up-1 ; i >= 1; i--) cnt[i]+=cnt[i+1]; 94 int res = 0 ; 95 for ( int i = 1 ; i <=up ; i++) 96 res+=cnt[i]; 97 return res; 98} 99int main() 100{ 101 #ifndef ONLINE_JUDGE 102 freopen("code/in.txt","r",stdin); 103 #endif 104 int T; 105 scanf("%d",&T); 106 while (T--) 107 { 108 scanf("%s",s); 109 int len = getSuffix(s); 110 LL ans = 1LL*len*(len-1)/2; 111 ans-=1LL*solve(len); 112 printf("%lld\n",ans); 113 } 114 #ifndef ONLINE_JUDGE 115 fclose(stdin); 116 #endif 117 return 0; 118}

题目链接 题意：给出一个字符串，问所有不同的字串的个数。 思路：直接求比较困难。我们考虑，假如组成字符串的所有字符都不相同，那么就没有相同的字串。假设字符串的长度为 n，那么长度为 1 的子串有 n 个，为 2 的有 n-1 个……为 n 的有 1 个，一共就是 n*(n+1)/2 个，但是实际上会有重复的。

poj3261 题意：给一个字符串，要求找出至少出现k次的最长重复子串… 思路：后缀数组，然后再次用到了根据height数组对后缀进行分组的套路…二分判定合法性，对于当前的最长长度x，分组使得每组中的height[i]都大于等于x，所不同的是，判定变成了存在一个组，后缀的个数至少为k个（因为这样，就可以对于大于等于k个的后缀，同时取前x长度，得到的就是出现了至少k次且长度为x的前缀）1A，蛤蛤蛤

poj 1743 题意：n 个数字（1..88）表示的音符，问最长的连续两段长度至少为 5 的变化相同的音符段的长度。 思路：求最长重复字串，很容易想到后缀数组，但是这道题多了一个不可重叠的要求。

ural1517 题意：给出两个字符串，求最长的公共字串（要求出具体的字符串是什么） 思路：依然是后缀数组，在更新长度 的时候记录起始位置即可，1A。以及，发现多开了一个完全没有必要的数组w[]，这次已删。

poj 2774 题意：给出两个字符串，问最长的公共连续字串。 思路：后缀数组模板题。 具体可以参考两篇国集论文（09，04） topcoder中的讲解 codechef上的讲解 还有一篇讲 dc3算法的论文： 这里不谈具体的后缀数组的学习内容，说说大概的学习过程。

原文链接：链接 讲了后缀数组的概念，然后从最暴力的 O(nnlogn) 的复杂度（O(n) 用来比较字符串，O(nlogn) 是排序的复杂度）逐步优化，依据各个串之间的关系，大概讲了倍增算法，以及给出了一篇 The Skew Algorithm 的论文。