New Distinct Substrings

题目链接：spoj - SUBST1

题意：给你一个串，求他的子串个数

思路：每个子串都是某个后缀的前缀，所以计算每个后缀的贡献即可，按照后缀suffix(sa[1])，suffix(sa[2])…的顺序计算，当加入suffix(sa[k])时，本应产生n-sa[k]+1个前缀，但是有height[k]个前缀在前面已经计算过了，所以suffix(sa[k])对答案的贡献就是n-sa[k]+1-height[k]

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 50010;

int wa[N], wb[N], wv[N], wss[N];
int n, T, rak[N], height[N], cal[N], sa[N];
char s[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        for (int i = 1; i <= n; i++) cal[i] = s[i];
        cal[n + 1] = 0;
        da(cal + 1, sa, n + 1, 150);
        calc(cal + 1, sa, n);
        int res = 0;
        for (int i = 1; i <= n; i++)
            res = res + n - sa[i] + 1 - height[i];
        printf("%d\n", res);
    }
    return 0;
}

Substring

题目链接：hdu - 5769

题意：给你一个串和一个字符x，求包含字符x的子串个数

思路：和上题思路一样，计算每个后缀的贡献，不同的是子串中需要包含字符x，所以我们可以先预处理出每个位置后面离它最近的一个字符x的位置pos[]，当加入suffix(sa[k])时，我们只能从pos[sa[k]]开始取前缀，所以suffix(sa[k])对答案的贡献就是n-sa[k]+1-max(height[k]，pos[sa[k]]-sa[k])

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 700010;

int wa[N], wb[N], wv[N], wss[N];
int rak[N], height[N], cal[N], sa[N];
int T, icas, pos[N];
char s[N], ch[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%s%s", ch + 1, s + 1);
        int n = strlen(s + 1);
        for (int i = 1; i <= n; i++) cal[i] = s[i];
        cal[n + 1] = 0;
        da(cal + 1, sa, n + 1, 200);
        calc(cal + 1, sa, n);
        int p = n + 1;
        for (int i = n; i >= 1; i--) {
            if (s[i] == ch[1]) p = i;
            pos[i] = p;
        }
        ll res = 0;
        for (int i = 1; i <= n; i++) {
            res = res + n - sa[i] + 1;
            res -= max(height[i], pos[sa[i]] - sa[i]);
        }
        printf("Case #%d: %lld\n", ++icas, res);
    }
    return 0;
}

Musical Theme

题目链接：poj - 1743

题意：给你一个串，找出最长、不可重叠、重复的子串

思路：二分答案，将问题转换为判定型问题，判断是否存在两个子串长度为k且不重叠，将排序后的后缀分为若干组，每组内所有元素的height大于等于k，那么每组内任意两个后缀的最长公共前缀长度都大于等于k，此时如果有一组内sa的最大值与最小值之差大于等于k，那么就一定存在两个子串长度为k且不重叠

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20010;
const int INF = 0x3f3f3f3f;

int wa[N], wb[N], wv[N], wss[N], a[N];
int n, rak[N], height[N], cal[N], sa[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

bool check(int mid)
{
    int imin = sa[1], imax = sa[1];
    for (int i = 2; i <= n; i++) {
        if (height[i] >= mid) {
            imin = min(imin, sa[i]);
            imax = max(imax, sa[i]);
        }
        else {
            if (imax - imin > mid) return true;
            imin = imax = sa[i];
        }
    }
    return imax - imin > mid;
}

int main()
{
    while (scanf("%d", &n) && 0 != n) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) {
            cal[i] = a[i] - a[i - 1];
            cal[i] += 90;
        }
        cal[n + 1] = 0;
        da(cal + 1, sa, n + 1, 200);
        calc(cal + 1, sa, n);
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(mid)) l = mid + 1;
            else r = mid;
        }
        printf("%d\n", l >= 5 ? l : 0);
    }
    return 0;
}

Milk Patterns

题目链接：poj - 3261

题意：给你一个数组和一个数k，求出最长、可以重叠、重复k次的子串

思路：二分答案，将问题转换为判定型问题，判断是否存在k个子串长度为L、可以重叠的子串，将排序后的后缀分为若干组，每组内所有元素的height大于等于L，此时如果存在一组组内后缀的数目大于等于k，那么就一定存在k个子串长度为L、可以重叠的子串

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1000010;

int wa[N], wb[N], wv[N], wss[N], a[N];
int n, k, rak[N], height[N], cal[N], sa[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

bool check(int mid)
{
    int cnt = 1;
    for (int i = 2; i <= n; i++) {
        if (height[i] >= mid) cnt++;
        else cnt = 1;
        if (cnt >= k) return true;
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cal[i]);
        cal[i]++;
    }
    cal[n + 1] = 0;
    da(cal + 1, sa, n + 1, N);
    calc(cal + 1, sa, n);
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    printf("%d\n", l);
    return 0;
}

Life Forms

题目链接：poj - 3294

题意：给你n个字符串，求在大于n/2个字符串中含有的最长公共子串

思路：将n个字符串拼接起来，中间用一个从没出现过且不相同的字符隔开，求出后缀数组后二分答案，将排序后的后缀分为若干组，判断每一组内的后缀是否出现在大于n/2个不同的字符串中(标记某个字符串是否出现过，统计不同字符串的数量)

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 101500;
const int M = 110;

int wa[N], wb[N], wv[N], wss[N];
int rak[N], height[N], cal[N], sa[N];
int n, len, belong[N];
bool f[M];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

bool check(int k)
{
    memset(f, false, sizeof(f));
    int cnt = 0;
    for (int i = 1; i <= len; i++) {
        if (height[i] >= k) {
            if (0 != belong[sa[i]] && false == f[belong[sa[i]]]) {
                cnt++;
                f[belong[sa[i]]] = true;
            }
        }
        else {
            memset(f, false, sizeof(f));
            if (0 != belong[sa[i]]) {
                cnt = 1;
                f[belong[sa[i]]] = true;
            }
            else cnt = 0;
        }
        if (cnt > n / 2) return true;
    }
    return false;
}

int main()
{
    while (scanf("%d", &n) && 0 != n) {
        int b = 125;
        len = 0;
        for (int i = 1; i <= n; i++) {
            char s[10 * M];
            scanf("%s", s + 1);
            for (int k = 1; k <= strlen(s + 1); k++) {
                cal[++len] = s[k];
                belong[len] = i;
            }
            if (i != n) {
                cal[++len] = b++;
                belong[len] = 0;
            }
        }
        cal[len + 1] = 0;
        belong[len + 1] = 0;
        da(cal + 1, sa, len + 1, 250);
        calc(cal + 1, sa, len);
        int l = 0, r = len;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        if (0 == l) {
            printf("?\n\n");
            continue;
        }
        memset(f, false, sizeof(f));
        int cnt = 0;
        for (int i = 1; i <= len; i++) {
            if (height[i] >= l) {
                if (0 != belong[sa[i]] && false == f[belong[sa[i]]]) {
                    cnt++;
                    f[belong[sa[i]]] = true;
                }
            }
            else {
                if (cnt > n / 2) {
                    for (int j = 0; j < l; j++) printf("%c", char(cal[sa[i - 1] + j]));
                    printf("\n");
                }
                memset(f, false, sizeof(f));
                if (0 != belong[sa[i]]) {
                    cnt = 1;
                    f[belong[sa[i]]] = true;
                }
                else cnt = 0;
            }
        }
        printf("\n");
    }
    return 0;
}

Relevant Phrases of Annihilation

题目链接：spoj - PHRASES

题意：给你n个字符串，求在每个字符串中不重叠的至少出现2次的最长子串

思路：将n个字符串拼接起来，中间用一个从没出现过且不相同的字符隔开，求后缀数组后二分答案，将排序后的后缀分为若干组，判断是否有一组后缀在每个原来的字符串中至少出现两次，并且在每个原来的字符串中，后缀的起始位置的最大值与最小值之差是否不小于当前二分的长度

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100500;
const int M = 10010;
const int INF = 0x3f3f3f3f;

int wa[N], wb[N], wv[N], wss[N];
int rak[N], height[N], cal[N], sa[N];
int n, T, len, belong[N];
int f[12], imin[12], imax[12];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

bool check(int k)
{
    memset(f, 0, sizeof(f));
    memset(imin, INF, sizeof(imin));
    memset(imax, 0, sizeof(imax));
    int cnt = 0;
    for (int i = 1; i <= len; i++) {
        if (height[i] >= k) {
            if (0 != belong[sa[i]] && 0 == f[belong[sa[i]]]) cnt++;
            f[belong[sa[i]]]++;
            imin[belong[sa[i]]] = min(imin[belong[sa[i]]], sa[i]);
            imax[belong[sa[i]]] = max(imax[belong[sa[i]]], sa[i]);
        }
        else {
            memset(f, 0, sizeof(f));
            memset(imin, INF, sizeof(imin));
            memset(imax, 0, sizeof(imax));
            if (0 != belong[sa[i]]) {
                cnt = 1;
                f[belong[sa[i]]]++;
                imin[belong[sa[i]]] = min(imin[belong[sa[i]]], sa[i]);
                imax[belong[sa[i]]] = max(imax[belong[sa[i]]], sa[i]);
            }
            else cnt = 0;
        }
        if (cnt == n) {
            bool flag = true;
            for (int i = 1; i <= n; i++) {
                if (f[belong[sa[i]]] < 2) flag = false;
                if (imax[i] - imin[i] < k) flag = false;
            }
            if (flag) return true;
        }
    }
    return false;
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        len = 0;
        int b = 125;
        for (int i = 1; i <= n; i++) {
            char s[M];
            scanf("%s", s + 1);
            for (int k = 1; k <= strlen(s + 1); k++) {
                cal[++len] = s[k];
                belong[len] = i;
            }
            if (i != n) cal[++len] = ++b;
        }
        cal[len + 1] = 0;
        da(cal + 1, sa, len + 1, 150);
        calc(cal + 1, sa, len);
        int l = 0, r = len;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}

Long Long Message

题目链接：poj - 2774

题意：给你两个串，求两个串的最长公共子串

思路：将第二个串写在第一个串的后面，中间用一个没有出现过的字符隔开，求这个新字符串的后缀数组，当sa[i-1]和sa[i]不属于同一个字符串时，height[i]的最大值就是答案

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 200010;

int wa[N], wb[N], wv[N], wss[N];
int n, T, rak[N], height[N], cal[N], sa[N];
char a[N], b[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

int main()
{
    scanf("%s%s", a + 1, b + 1);
    int la = strlen(a + 1), lb = strlen(b + 1);
    for (int i = 1; i <= la; i++) cal[i] = a[i];
    cal[la + 1] = 0;
    for (int i = 1; i <= lb; i++) cal[i + la + 1] = b[i];
    int n = la + lb + 1;
    cal[n + 1] = 0;
    da(cal + 1, sa, n + 1, 150);
    calc(cal + 1, sa, n);
    int res = 0;
    for (int i = 2; i <= n; i++) {
        if (sa[i - 1] < la + 1 && sa[i] > la + 1) res = max(res, height[i]);
        else if (sa[i - 1] > la + 1 && sa[i] < la + 1) res = max(res, height[i]);
    }
    printf("%d\n", res);
    return 0;
}

Substrings

题目链接：poj - 1226

题意：给你n个串，求顺序出现或者逆序出现在每个字符串的最长子串

思路：将每个字符串反过来写一遍，再将这2*n个字符串拼接起来，中间用一个从没出现过且不相同的字符隔开，求出后缀数组后二分答案，判断是否有一组后缀在每个原来的字符串或反转后的字符串中出现，注意特判n=1的情况

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20500;
const int M = 110;
const int INF = 0x3f3f3f3f;

int wa[N], wb[N], wv[N], wss[N];
int rak[N], height[N], cal[N], sa[N];
int n, T, len, belong[N];
bool f[M];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

bool check(int k)
{
    memset(f, false, sizeof(f));
    int cnt = 0;
    for (int i = 1; i <= len; i++) {
        if (height[i] >= k) {
            if (0 != belong[sa[i]] && false == f[belong[sa[i]]]) {
                cnt++;
                f[belong[sa[i]]] = true;
            }
        }
        else {
            memset(f, false, sizeof(f));
            if (0 != belong[sa[i]]) {
                cnt = 1;
                f[belong[sa[i]]] = true;
            }
            else cnt = 0;
        }
        if (cnt == n) return true;
    }
    return false;
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if (1 == n) {
            char s[M];
            scanf("%s", s + 1);
            printf("%d\n", strlen(s + 1));
            continue;
        }
        len = 0;
        int b = 125;
        for (int i = 1; i <= n; i++) {
            char s[M];
            scanf("%s", s + 1);
            for (int k = 1; k <= strlen(s + 1); k++) {
                cal[++len] = s[k] + 1;
                belong[len] = i;
            }
            cal[++len] = ++b;
            for (int k = strlen(s + 1); k >= 1; k--) {
                cal[++len] = s[k] + 1;
                belong[len] = i;
            }
            if (i != n) cal[++len] = ++b;
        }
        cal[len + 1] = 0;
        da(cal + 1, sa, len + 1, 350);
        calc(cal + 1, sa, len);
        int l = 0, r = len;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}

Mr. Panda and Fantastic Beasts

题目链接：Gym - 101194F

题意：给你n个字符串，找到第一个字符串字典序最小的最短子串，使得这个子串不是其他字符串的子串

思路：将n个字符串拼接起来，中间用一个从没出现过且不相同的字符隔开，求出后缀数组后，对所有来自第一个字符串的后缀进行判断，找到它左边第一个不是来自第一个串的后缀，求lcp为x，找到它右边第一个不是来自第一个串的后缀，求lcp为y，那么显然该后缀至少取前max(x,y)+1个字符做为子串，对每个后缀都进行一次判断，取最小值即可，注意需要判断max(x,y)+1是否超过了第一个字符串后缀的长度

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 300010;
const int INF = 0x3f3f3f3f;

int wa[N], wb[N], wv[N], wss[N];
int rak[N], height[N], cal[N], sa[N];
int rmq[N], imin[N][30], len1, icas;
int n, len, T, belong[N], lef[N], rig[N];
char s[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

void init(int n)
{
    memset(imin, 0, sizeof(imin));
    for (int i = 1; i <= n; i++) imin[i][0] = height[i];
    int l = int(log((double)n) / log(2.0));
    for (int j = 1; j <= l; j++) {
        for (int i = 1; i + (1 << (j - 1)) <= n; i++) {
            imin[i][j] = min(imin[i][j - 1], imin[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int ask(int l, int r)
{
    int k = int(log(double(r - l + 1)) / log(2.0));
    return min(imin[l][k], imin[r - (1 << k) + 1][k]);
}

int lcp(int a, int b)
{
    int ra = rak[a], rb = rak[b];
    if (ra > rb) swap(ra, rb);
    return ask(ra + 1, rb);
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int b = 125;
        len = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%s", s + 1);
            if (1 == i) len1 = strlen(s + 1);
            int tl = strlen(s + 1);
            for (int k = 1; k <= tl; k++) {
                cal[++len] = s[k];
                belong[len] = i;
            }
            if (i != n) {
                cal[++len] = ++b;
                belong[len] = 0;
            }
        }
        cal[len + 1] = 0;
        da(cal + 1, sa, len + 1, 50200);
        calc(cal + 1, sa, len);
        int lst = -1;
        for (int i = 1; i <= len; i++) {
            if (0 == belong[sa[i]]) continue;
            if (1 == belong[sa[i]]) lef[i] = lst;
            else lst = i;
        }
        lst = -1;
        for (int i = len; i >= 1; i--) {
            if (0 == belong[sa[i]]) continue;
            if (1 == belong[sa[i]]) rig[i] = lst;
            else lst = i;
        }
        init(len);
        int rc = INF, rp = 0;
        for (int i = 1; i <= len; i++) {
            if (1 != belong[sa[i]]) continue;
            int L = lef[i], R = rig[i], tc = 0;
            if (-1 != L) tc = max(tc, lcp(sa[i], sa[L]));
            if (-1 != R) tc = max(tc, lcp(sa[i], sa[R]));
            if (len1 - sa[i] + 1 > tc) {
                if (tc + 1 < rc) {
                    rc = tc + 1;
                    rp = sa[i];
                }
            }
        }
        printf("Case #%d: ", ++icas);
        if (INF == rc) {
            printf("Impossible\n");
            continue;
        }
        for (int i = 0; i < rc; i++) printf("%c", char(cal[rp + i]));
        printf("\n");
    }
    return 0;
}

Good Article Good sentence

题目链接：hdu - 4416

题意：给出一个串A和若干串B，问A中有多少子串未在任一B串中出现过

思路：将所有的串拼接起来，中间用一个从没出现过且不相同的字符隔开，求出后缀数组，设A串的长度为lenA，对于A串中每个后缀，lenA-sa[i]+1-height[i]就是没有限制条件下第i个后缀的贡献，设j为i后面第一个来自B串的后缀，那么加上限制条件后，每个后缀的贡献就是lenA-sa[i]+1-max(height[i],lcp(i,j))，lcp(i,j)可以通过从后向前扫一遍求出来

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 300500;
const int INF = 0x3f3f3f3f;

typedef long long ll;

int wa[N], wb[N], wv[N], wss[N];
int rak[N], height[N], cal[N], sa[N];
int T, n, len, len1, icas, lcp[N];
char s[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        len = 0;
        int b = 125;
        for (int i = 1; i <= n + 1; i++) {
            scanf("%s", s + 1);
            if (1 == i) len1 = strlen(s + 1);
            int len2 = strlen(s + 1);
            for (int k = 1; k <= len2; k++)
                cal[++len] = s[k];
            if (i != n + 1) cal[++len] = ++b;
        }
        cal[len + 1] = 0;
        da(cal + 1, sa, len + 1, 100500);
        calc(cal + 1, sa, len);
        int rl = 0;
        for (int i = len; i >= 1; i--) {
            if (sa[i] > len1) rl = height[i];
            else {
                lcp[i] = rl;
                rl = min(rl, height[i]);
            }
        }
        ll res = 0;
        for (int i = 1; i <= len; i++) {
            if (sa[i] <= len1) {
                ll t = ll(len1 - sa[i] + 1 - max(lcp[i], height[i]));
                res += t;
            }
        }
        printf("Case %d: %lld\n", ++icas, res);
    }
    return 0;
}

string string string

题目链接：hdu - 6194

题意：给出一个字符串，求恰好出现k次的子串个数

思路：求出后缀数组后，枚举长度为k的段，一段一段的枚举，用rmq求出每一段的最长公共前缀长度lcp，即这段有lcp个子串是满足出现k次的，但又有可能子串过短而不止出现k次，所以要减去出现次数大于k次的子串个数，所以每段对答案的贡献就是lcp-max(height[i],height[i+k])，特判k=1的情况

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 100010;
const int M = 30;
const int INF = 0x3f3f3f3f;

int wa[N], wb[N], wv[N], wss[N];
int rak[N], height[N], cal[N], sa[N];
int T, len, rmq[N], imin[N][M];
ll k;
char s[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

void init(int n)
{
    for (int i = 1; i <= n; i++) imin[i][0] = height[i];
    int l = int(log((double)n) / log(2.0));
    for (int j = 1; j <= l; j++) {
        for (int i = 1; i + (1 << (j - 1)) <= n; i++) {
            imin[i][j] = min(imin[i][j - 1], imin[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int ask(int l, int r)
{
    int k = int(log(double(r - l + 1)) / log(2.0));
    return min(imin[l][k], imin[r - (1 << k) + 1][k]);
}

int lcp(int a, int b)
{
    int ra = rak[a], rb = rak[b];
    if (ra > rb) swap(ra, rb);
    return ask(ra + 1, rb);
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%s", &k, s + 1);
        int ls = strlen(s + 1);
        len = 0;
        for (int i = 1; i <= ls; i++) cal[++len] = s[i];
        cal[len + 1] = 0;
        da(cal + 1, sa, len + 1, 150);
        calc(cal + 1, sa, len);
        init(len);
        ll res = 0;
        if (1 == k) {
            for (int i = 1; i <= len; i++)
                res += max(0, len - sa[i] + 1 - max(height[i], i + 1 > len ? 0 : height[i + 1]));
            printf("%lld\n", res);
            continue;
        }
        for (int i = 1; i + k - 1 <= len; i++) {
            int l = i, r = i + k - 1;
            int t = lcp(sa[l], sa[r]);
            res += max(0, t - max(height[l], r + 1 > len ? 0 : height[r + 1]));
        }
        printf("%lld\n", res);
        for (int i = 1; i <= ls; i++) s[i] = '\0';
    }
    return 0;
}

Boring String Problem

题目链接：hdu - 5008

题意：给出一个字符串，求出第k小的子串，并求出字符串的起止位置，如果有多个重复子串，求出位置最靠左的子串

思路：求出后缀数组，后缀数组本来就是按照字典序排序的，由于height数组的去重性质，我们就可以通过二分查找来定位第k小的子串来自哪个后缀，但由于可能有多个重复的子串，所以需要暴力向后面的后缀进行查找，找到位置最靠左的子串

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 100010;

typedef long long ll;

int wa[N], wb[N], wv[N], wss[N];
int rak[N], height[N], cal[N], sa[N];
int len, q;
ll b[N];
char s[N];

bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    for (i = 0; i < m; i++) wss[i] = 0;
    for (i = 0; i < n; i++) wss[x[i] = r[i]]++;
    for (i = 1; i < m; i++) wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; 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++) wss[i] = 0;
        for (i = 0; i < n; i++) wss[wv[i]]++;
        for (i = 1; i < m; i++) wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
        for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
            if (cmp(y, sa[i - 1], sa[i], j)) x[sa[i]] = p - 1;
            else x[sa[i]] = p++;
        }
    }
}

void calc(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rak[sa[i]] = i;
    for (i = 0; i < n; height[rak[i++]] = k)
        for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);
    for (i = n; i; i--) {
        rak[i] = rak[i - 1];
        sa[i]++;
    }
}

int main()
{
    while (scanf("%s", s + 1) != EOF) {
        int ls = strlen(s + 1);
        len = 0;
        for (int i = 1; i <= ls; i++) cal[++len] = s[i];
        cal[len + 1] = 0;
        da(cal + 1, sa, len + 1, 150);
        calc(cal + 1, sa, len);
        for (int i = 1; i <= len; i++)
            b[i] = b[i - 1] + len - sa[i] + 1 - height[i];
        scanf("%d", &q);
        int l = 0, r = 0;
        while (q--) {
            ll k;
            scanf("%lld", &k);
            k = (l ^ r ^ k) + 1;
            if (k > b[len]) {
                l = r = 0;
                printf("%d %d\n", l, r);
                continue;
            }
            int pos = lower_bound(b + 1, b + len + 1, k) - b;
            int t = k - b[pos - 1];
            l = sa[pos], r = sa[pos] + height[pos] + t - 1;
            int rd = r - l + 1;
            while (pos + 1 <= len && height[pos + 1] >= rd) {
                pos++;
                if (sa[pos] < l) {
                    l = sa[pos];
                    r = l + rd - 1;
                }
            }
            printf("%d %d\n", l, r);
        }
        for (int i = 1; i <= ls; i++) s[i] = '\0';
    }
    return 0;
}