BigHead
0%

奶牛序列

Posted on Edited on In , Views: Valine:

题意

  • 约翰刚帮奶牛们拍完照，拿着合影的他，看着奶牛队列，又莫名想到了一个字符串问题：
    我们将n头奶牛的队列看成一个长为n的字符串S，让Ti表示从第i的字符开始的后缀。求： 图片描述
  • 其中，len(a)表示字符串a的长度，lcp(a,b)表示字符串a和字符串b的最长公共前缀，输入字符串长度不超过5e5

    分析

1.

  • 首先前面的len(Ti)和len(Tj)可以提取出来一步算出来，剩下主要就是求
    lcp(Ti,Tj)的和，在后缀数组中求两个后缀的最长前缀长度，就是求各自对应h[i]数组间的最小值。由于这里i和j把所有的一对Ti和Tj组合都取遍，所以这里可以转换成求所有h[i]和h[j]数组中间的最小值的和的两倍

  • 那么问题转换成求所有h[i]和h[j]数组中间的最小值的和，，如何快速的求出所有和呢，因为枚举会T。这里用到nlogn求最长公共子序列的思想。每一次我只求所有h[j]和h[i]之间的最小值的和(其中j<i).

  • 然后不断的放入h[i],h[i]放入到第一个大于等于他的位置并把当前位置的值更新为 h[i]（因为所有大于h[i]的h[j]的值在和h[i]取最小之后多出来的那部分无效了，即使是在求i之后h[k]的所有lcp和也一样，由于存在h[i],那么h[j]在h[i]的左边并大于h[i]的部分无效，所以就直接用h[i]代替了h[j]）.同在在那个位置记录下最新的位置信息pos[k] = i。同时用一个数组sum[i]记录到位置i的lcp的和。

  • 如何计算sum（lcp(Tj,Ti)） j<i？，就拿h[i]插入后举例子，他的前一个h[i-1]一定小于h[i],那么那个位置的sum[i-1]就不需要更新了，直接拿来用。pos[i-1]和pos[i]之间的值就全部都是h[i]了，然后再更新sum[i].

  1. 好了经过上面很长的分析之后，我忘记sum(lcp)*2了

思考

  1. 这题想到就不难了，当然实现的时候还是要想半天的

  2. 求最长公共子序列这种nlogn的思想很实用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/*************************************************************************
	> File Name: l.cpp
	> Author: liangxianfeng
	> Mail:   641587852@qq.com
	> Created Time: 2016年05月05日 星期四 20时34分02秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int i =0; i < n; ++i)
#define CLR(x) memset(x,0,sizeof x)
#define MEM(a,b) memset(a,b,sizeof a)
#define pr(x) cout << #x << " = " << x << " ";
#define prln(x) cout << #x << " = " << x <<  endl; 
const int maxn = 6e5+100;
const int INF = 0x3f3f3f3f;
int wa[maxn], wb[maxn], wv[maxn], c[maxn], t[maxn];
bool cmp(int *r, int a, int b, int j) {
    return r[a] == r[b] && r[a+j] == r[b+j];
}
void getSa(int *r, int *sa, int n, int m) {
    int i, j, p, *x = wa, *y = wb;
    for(i = 0; i < m; ++i) c[i] = 0;
    for(i = 0;i < n; ++i) c[x[i] = r[i]]++;
    for(i = 0; i < m-1; ++i) c[i+1] += c[i];
    for(i = n-1; i >= 0; --i) sa[--c[x[i]]] = i;
    for(j = 1, p = 1; p < n; m = p, j <<=1) {
        for(i = n-j, p = 0; i < n; i++) y[p++] = i;
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[p++] = sa[i] - j;
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];
        for(i = 0; i < m; ++i) c[i] = 0;
        for(i = 0; i < n; ++i) c[wv[i]]++;
        for(i = 0; i < m-1; ++i) c[i+1] += c[i];
        for(i = n-1; i >= 0; --i) sa[--c[wv[i]]] = y[i];
        swap(x,y);
        x[sa[0]] = 0;
        for(i = 1, p = 1; i < n; ++i){
            x[sa[i]] = cmp(y, sa[i], sa[i-1], j)?p-1:p++;
        }
    }
}
int rank[maxn], height[maxn];
void getHeight(int *r, int *sa, int n) {
    int i, j, k = 0;
    for(int i = 1; i <= n; ++i) rank[sa[i]] = i;
    for(i = 0; i < n; height[rank[i++]] = k){
        for(k?k--:0,j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);
    }
}
char ss[maxn];
int num[maxn];
int sa[maxn];
ll a[maxn], pos[maxn];
ll sum[maxn];
int main(){
#ifdef LOCAL
	freopen("/home/zeroxf/桌面/in.txt","r",stdin);
	//freopen("/home/zeroxf/桌面/out.txt","w",stdout);
#endif
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%s", ss);
        int len = strlen(ss);
        for(int i = 0; i < len; ++i) {
            num[i] = ss[i];
        }
        num[len] = 0;
        getSa(num, sa, len+1, 150);
        getHeight(num, sa, len);
        height[1] = 0;
        int now = 1;
        for(int i = 0; i <= len; ++i) sum[i] = 0;
        a[0] = height[1];
        pos[0] = 1;
        ll ans = 0;
        for(ll i = len; i >= 1; --i) ans += (len-1)*i;
        for(ll i = 2; i <= len; ++i){
            int p = lower_bound(a,a+now,height[i]) - a;
            if(p==0){
                sum[0] = (i-1)*height[i];
                ans -= 2*sum[0];
            }
            else if(p >= now) {
                sum[p] = sum[p-1] + height[i];
                ans -= 2*sum[p];
            }else {
                sum[p] =  sum[p-1] + height[i]*(i-pos[p-1]);
                ans -= 2*(sum[p] );
            }
            a[p] = height[i];
            pos[p] = i;
            now = p+1;
        }
        printf("%lld\n", ans);
    }
	return 0;
}