Blackops

初心易得，始终难守

0%

HDU 4622 Reincarnation（后缀数组+RMQ | 后缀自动机）

发表于 更新于 分类于 ， ，

Reincarnation

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 3975 Accepted Submission(s): 1573

Problem Description
Now you are back,and have a task to do:
Given you a string s consist of lower-case English letters only,denote f(s) as the number of distinct sub-string of s.
And you have some query,each time you should calculate f(s[l…r]), s[l…r] means the sub-string of s start from l end at r.

Input
The first line contains integer T(1<=T<=5), denote the number of the test cases.
For each test cases,the first line contains a string s(1 <= length of s <= 2000).
Denote the length of s by n.
The second line contains an integer Q(1 <= Q <= 10000),denote the number of queries.
Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n), denote a query.

Output
For each test cases,for each query,print the answer in one line.

Sample Input
2
bbaba
5
3 4
2 2
2 5
2 4
1 4
baaba
5
3 3
3 4
1 4
3 5
5 5

Sample Output
3
1
7
5
8
1
3
8
5
1

题目链接：HDU 4622
题意就是询问某段区间形成的子串其自身不同子串的个数，显然对于每一个询问做一次后缀数组不太现实$O(Q*(NlogN+N))$，那么可以参照普通求完整串的不同子串的方法来写，完整串的求法就是将后缀按照$rank$排序，然后减去相邻后缀之间的最长公共前缀值。
如果放到区间呢？就是把所有$sa$值在区间内的点选出来，然后要让这些点也按照后缀字典序升序，但是如果按照原来完整串的顺序，遍历过来选出的$rank$不一定是把区间子串做一遍$SA$求得的$rank$，那怎么办呢？分类讨论来更新从而维护实际对于区间内子串$rank$值的上升性质，我是枚举$rank$值来遍历的，可以发现合法的只有两种情况：当$sa[i] \lt sa[last\_rank]$或者$(sa[i] \gt sa[last\_rank]) \&\& (LCP(i,last\_rank) \lt len\_i)$时$i$才会大于$last\_rank$，才能用于更新，debug了很久终于造了一组区别正确与错误的数据，可以输出选中的$SA$值看看一下：
2

后缀自动机的做法就是用$ans[i][j]$表示区间$(i,j)$的答案，然后两个for暴力处理出所有答案，由于每次加入一个字母后，增加的子串个数是$L[last].len-L[L[last].pre].len$；
那么$ans[i][j] = ans[i][j-1] + L[last].len - L[L[last].pre].len$

abacababacab
10
1 7

正确答案是21，直接更新不分类讨论是23

SA代码：

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 2010;
int wa[N], wb[N], sa[N], cnt[N], ran[N], height[N];
char s[N];

inline bool cmp(int r[], int a, int b, int d)
{
    return r[a] == r[b] && r[a + d] == r[b + d];
}
void DA(int n, int m)
{
    int i, *x = wa, *y = wb;
    for (i = 0; i < m; ++i)
        cnt[i] = 0;
    for (i = 0; i < n; ++i)
        ++cnt[x[i] = s[i]];
    for (i = 1; i < m; ++i)
        cnt[i] += cnt[i - 1];
    for (i = n - 1; i >= 0; --i)
        sa[--cnt[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int p = 0;
        for (i = n - k; i < n; ++i)
            y[p++] = i;
        for (i = 0; i < n; ++i)
            if (sa[i] >= k)
                y[p++] = sa[i] - k;
        for (i = 0; i < m; ++i)
            cnt[i] = 0;
        for (i = 0; i < n; ++i)
            ++cnt[x[y[i]]];
        for (i = 1; i < m; ++i)
            cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; --i)
            sa[--cnt[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (i = 1; i < n; ++i)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
        m = p;
        if (m >= n)
            break;
    }
}
void gethgt(int n)
{
    int i, k = 0;
    for (i = 1; i <= n; ++i)
        ran[sa[i]] = i;
    for (i = 0; i < n; ++i)
    {
        if (k)
            --k;
        int j = sa[ran[i] - 1];
        while (s[j + k] == s[i + k])
            ++k;
        height[ran[i]] = k;
    }
}
namespace rmq
{
    int dp[N][12];
    void init(int l, int r)
    {
        CLR(dp, 0);
        for (int i = l; i <= r; ++i)
            dp[i][0] = height[i];
        for (int j = 1; l + (1 << j) - 1 <= r; ++j)
        {
            for (int i = l; i + (1 << j) - 1 <= r; ++i)
                dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
    inline int ST(int l, int r)
    {
        int len = r - l + 1, k = 0;
        while ((1 << (k + 1)) <= len)
            ++k;
        return min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }
    int lcp(int rl, int rr, int len)
    {
        if (rl > rr)
            swap(rl, rr);
        if (rl == rr)
            return len;
        ++rl;
        return ST(rl, rr);
    }
}
int main(void)
{
    int T, i;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", s);
        int len = strlen(s);
        DA(len + 1, 'z' + 1);
        gethgt(len);
        rmq::init(1, len);
        int q, l, r;
        scanf("%d", &q);
        while (q--)
        {
            scanf("%d%d", &l, &r);
            --l;
            --r;
            int ans = (r - l + 1) * (r - l + 2) / 2;
            int lastrank = -1;
            for (i = 1; i <= len; ++i)
            {
                if (sa[i] >= l && sa[i] <= r)
                {
                    if (lastrank == -1)
                        lastrank = i;
                    else
                    {
                        int lenlast = r - sa[lastrank] + 1, leni = r - sa[i] + 1;
                        int lcp = rmq::lcp(lastrank, i, len);
                        ans -= min({lcp,  lenlast, leni});
                        if (sa[i] < sa[lastrank] || (sa[i] > sa[lastrank] && lcp < leni))
                            lastrank = i;
                    }
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

SAM代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 2010;
struct Trie
{
    int nxt[26], pre, len;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        pre = -1;
        len = 0;
    }
} L[N << 1];
int sz, last;
int dp[N][N];
char s[N];

void init()
{
    sz = last = 0;
    L[sz++].init();
}
inline int newnode()
{
    L[sz].init();
    return sz++;
}
void ins(int c)
{
    int u = newnode();
    L[u].len = L[last].len + 1;
    int t = last;
    while (~t && L[t].nxt[c] == -1)
    {
        L[t].nxt[c] = u;
        t = L[t].pre;
    }
    if (t == -1)
        L[u].pre = 0;
    else
    {
        int v = L[t].nxt[c];
        if (L[t].len + 1 == L[v].len)
            L[u].pre = v;
        else
        {
            int np = newnode();
            L[np] = L[v];
            L[np].len = L[t].len + 1;
            L[u].pre = L[v].pre = np;
            while (t != -1 && L[t].nxt[c] == v)
            {
                L[t].nxt[c] = np;
                t = L[t].pre;
            }
        }
    }
    last = u;
}
int main(void)
{
    int TC, i, m, j;
    scanf("%d", &TC);
    while (TC--)
    {
        scanf("%s", s);
        int len = strlen(s);
        for (i = 0; i < len; ++i)
        {
            init();
            for (j = i; j < len; ++j)
            {
                ins(s[j] - 'a');
                dp[i][j] = dp[i][j - 1] + L[last].len - L[L[last].pre].len;
            }
        }
        scanf("%d", &m);
        while (m--)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", dp[l - 1][r - 1]);
        }
    }
    return 0;
}