本文共 2968 字，大约阅读时间需要 9 分钟。
题意：有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。
链接：
第一道后缀数组题，测了一下模板
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 typedef long long ll; 13 #define cl(a) memset(a,0,sizeof(a)) 14 #define ts printf("*****\n"); 15 int n,m,tt; 16 /* 17 *suffix array 18 *倍增算法 O(n*logn) 19 *待排序数组长度为n,放在0~n-1中，在最后面补一个0 20 *da(str ,n+1,sa,rank,height, , );//注意是n+1; 21 *例如： 22 *n = 8; 23 *num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0 24 *rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值 25 *sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值 26 *height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值 27 * 28 */ 29 const int MAXN=20010; 30 31 char str[MAXN]; 32 int r[MAXN]; 33 int sa[MAXN]; 34 int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值 35 //待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m, 36 //除s[n-1]外的所有s[i]都大于0，r[n-1]=0 37 //函数结束以后结果放在sa数组中 38 bool cmp(int *r,int a,int b,int l) 39 { 40 return r[a] == r[b] && r[a+l] == r[b+l]; 41 } 42 void da(int str[],int sa[],int rank[],int height[],int n,int m) 43 { 44 n++; 45 int i, j, p, *x = t1, *y = t2; 46 //第一轮基数排序，如果s的最大值很大，可改为快速排序 47 for(i = 0;i < m;i++)c[i] = 0; 48 for(i = 0;i < n;i++)c[x[i] = str[i]]++; 49 for(i = 1;i < m;i++)c[i] += c[i-1]; 50 for(i = n-1;i >= 0;i--)sa[--c[x[i]]] = i; 51 for(j = 1;j <= n; j <<= 1) 52 { 53 p = 0; 54 //直接利用sa数组排序第二关键字 55 for(i = n-j; i < n; i++)y[p++] = i;//后面的j个数第二关键字为空的最小 56 for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j; 57 //这样数组y保存的就是按照第二关键字排序的结果 58 //基数排序第一关键字 59 for(i = 0; i < m; i++)c[i] = 0; 60 for(i = 0; i < n; i++)c[x[y[i]]]++; 61 for(i = 1; i < m;i++)c[i] += c[i-1]; 62 for(i = n-1; i >= 0;i--)sa[--c[x[y[i]]]] = y[i]; 63 //根据sa和x数组计算新的x数组 64 swap(x,y); 65 p = 1; x[sa[0]] = 0; 66 for(i = 1;i < n;i++) 67 x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++; 68 if(p >= n)break; 69 m = p;//下次基数排序的最大值 70 } 71 int k = 0; 72 n--; 73 for(i = 0;i <= n;i++)rank[sa[i]] = i; 74 for(i = 0;i < n;i++) 75 { 76 if(k)k--; 77 j = sa[rank[i]-1]; 78 while(str[i+k] == str[j+k])k++; 79 height[rank[i]] = k; 80 } 81 } 82 int rank[MAXN],height[MAXN]; 83 int s[MAXN]; 84 bool check(int n,int k) 85 { 86 int Max=sa[1],Min=sa[1]; 87 for(int i=2;i<=n;i++) 88 { 89 if(height[i] Max)Max=sa[i]; 94 if(Max-Min>k)return true; 95 } 96 } 97 return false; 98 } 99 int main()100 {101 #ifndef ONLINE_JUDGE102 freopen("1.in","r",stdin);103 #endif104 while(scanf("%d",&n)==1 && n)105 {106 for(int i=0;i 0;i--)s[i]=s[i]-s[i-1]+90;108 n--;//减少一个长度109 for(int i=0;i
转载于:https://www.cnblogs.com/cnblogs321114287/p/4493752.html