【题解】HackerRank-Pseudo-Isomorphic Substrings

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/pseudo-isomorphic-substrings/problem

题意

对于一个字符串的每个前缀，求不同构的子串个数。

两个串同构定义为可以通过字符的双射变成相同的串。

题解

解法 1

  • 将原串翻转，改为求解每个后缀。
  • 考虑每个串的最小表示法（也就是用与之同构的字典序最小的串表示），如果我能快速比较两个串最小表示的字典序大小，以及求出两个串最小表示的 LCP，那么我可以往 SET 里依次插入每一个后缀，维护后缀长度和减最小表示字典序相邻的串的最小表示的 LCP 之和，那么就成功维护了答案。
  • 对于每一种字母建后缀数组（把所有其他字符当成一样的），对于一个串，考虑每一个字母的字典序，小的应该映射成 a，次小的为 b，以此类推。可以用排序求出每个后缀到其最小表示的映射关系。（这个映射关系也可以扫一遍维护。）
  • 两个串最小表示的 LCP 就是对映射后为 a-z 的字母串分别求 LCP 然后取 min。而有了 LCP 和映射关系，也能方便比较两个串的字典序（只需要比较最小表示第一个不同的字符映射后的字符）。
  • 复杂度 \(\mathrm{O}(26n\log (26n)+26n\log n)\)，需要一些常数优化技巧。

代码（其实我还有一份后缀自动机的代码，但是常数和空间都大了那么一点，没法 AC）

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
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[34;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// ----------------------------------------------------------------------------

// len = str.len + 1, rk [0..len-1] -> [1..len], sa/ht [1..len]
template<size_t size>
struct SuffixArray {
    bool type[size << 1];
    int bucket[size], bucket1[size];
    int sa[size], rk[size], ht[size];
    inline bool isLMS(const int i, const bool *type) { return i > 0 && type[i] && !type[i - 1]; }
    template<class T>
    inline void inducedSort(T s, int *sa, const int len, const int sigma, const int bucketSize, bool *type, int *bucket, int *cntbuf, int *p) {
        memset(bucket, 0, sizeof(int) * sigma);
        memset(sa, -1, sizeof(int) * len);
        for (int i = 0; i < len; i++) bucket[s[i]]++;
        cntbuf[0] = bucket[0];
        for (int i = 1; i < sigma; i++) cntbuf[i] = cntbuf[i - 1] + bucket[i];
        for (int i = bucketSize - 1; i >= 0; i--) sa[--cntbuf[s[p[i]]]] = p[i];
        for (int i = 1; i < sigma; i++) cntbuf[i] = cntbuf[i - 1] + bucket[i - 1];
        for (int i = 0; i < len; i++) if (sa[i] > 0 && !type[sa[i] - 1]) sa[cntbuf[s[sa[i] - 1]]++] = sa[i] - 1;
        cntbuf[0] = bucket[0];
        for (int i = 1; i < sigma; i++) cntbuf[i] = cntbuf[i - 1] + bucket[i];
        for (int i = len - 1; i >= 0; i--) if (sa[i] > 0 && type[sa[i] - 1]) sa[--cntbuf[s[sa[i] - 1]]] = sa[i] - 1;
    }
    template<typename T>
    inline void sais(T s, int *sa, int len, bool *type, int *bucket, int *bucket1, int sigma) {
        int i, j, bucketSize = 0, cnt = 0, p = -1, x, *cntbuf = bucket + sigma;
        type[len - 1] = 1;
        for (i = len - 2; i >= 0; i--) type[i] = s[i] < s[i + 1] || (s[i] == s[i + 1] && type[i + 1]);
        for (i = 1; i < len; i++) if (type[i] && !type[i - 1]) bucket1[bucketSize++] = i;
        inducedSort(s, sa, len, sigma, bucketSize, type, bucket, cntbuf, bucket1);
        for (i = bucketSize = 0; i < len; i++) if (isLMS(sa[i], type)) sa[bucketSize++] = sa[i];
        for (i = bucketSize; i < len; i++) sa[i] = -1;
        for (i = 0; i < bucketSize; i++) {
            x = sa[i];
            for (j = 0; j < len; j++) {
                if (p == -1 || s[x + j] != s[p + j] || type[x + j] != type[p + j]) { cnt++, p = x; break; }
                else if (j > 0 && (isLMS(x + j, type) || isLMS(p + j, type))) break;
            }
            x = (~x & 1 ? x >> 1 : x - 1 >> 1), sa[bucketSize + x] = cnt - 1;
        }
        for (i = j = len - 1; i >= bucketSize; i--) if (sa[i] >= 0) sa[j--] = sa[i];
        int *s1 = sa + len - bucketSize, *bucket2 = bucket1 + bucketSize;
        if (cnt < bucketSize) sais(s1, sa, bucketSize, type + len, bucket, bucket1 + bucketSize, cnt);
        else for (i = 0; i < bucketSize; i++) sa[s1[i]] = i;
        for (i = 0; i < bucketSize; i++) bucket2[i] = bucket1[sa[i]];
        inducedSort(s, sa, len, sigma, bucketSize, type, bucket, cntbuf, bucket2);
    }
    template<typename T>
    inline void getHeight(T s, const int len, const int *sa) {
        for (int i = 0, k = 0; i < len; i++) {
            if (rk[i] == 0) k = 0;
            else {
                if (k > 0) k--;
                int j = sa[rk[i] - 1];
                while (i + k < len && j + k < len && s[i + k] == s[j + k]) k++;
            }
            ht[rk[i]] = k;
        }
    }
    template<class T>
    inline void init(T s, int len, int sigma) {
        sais(s, sa, ++len, type, bucket, bucket1, sigma);
        for (int i = 1; i < len; i++) rk[sa[i]] = i;
        getHeight(s, len, sa);
    }
};

const int N = 1E5 + 100, M = 26E5 + 100;
int a[M];
char s[N];
SuffixArray<M> sa;
struct P { int p, c; };
P rp[N][26];
int mp[N][26];

struct RMQ {
    int f[22][M];
    inline int highbit(int x) { return 31 - __builtin_clz(x); }
    void init(int* v, int n) {
        FOR (i, 0, n) f[0][i] = v[i];
        FOR (x, 1, highbit(n) + 1)
            FOR (i, 0, n - (1 << x) + 1)
                f[x][i] = min(f[x - 1][i], f[x - 1][i + (1 << (x - 1))]);
    }
    int get_min(int l, int r) {
        if (l > r) swap(l, r);
        int t = highbit(r - ++l + 1);
        return min(f[t][l], f[t][r - (1 << t) + 1]);
    }
} rmq;

int lcp(int a, int b) {
    int ret = N;
    FOR (i, 0, 26) ret = min(ret, rmq.get_min(rp[a][i].p, rp[b][i].p));
    return ret;
}
int ll;
inline bool cmp(int a, int b, int lcp) {
    if (a + lcp >= ll || b + lcp >= ll) return a > b;
    return mp[a][s[a + lcp] - 'a'] < mp[b][s[b + lcp] - 'a'];
}
struct CMP { bool operator() (const int& a, const int& b){ return cmp(a, b, lcp(a, b)); }};

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    scanf("%s", s);
    ll = strlen(s);
    reverse(s, s + ll);
    int pp = 0;
    FOR (c, 0, 26) {
        FOR (i, 0, ll) {
            int cc = s[i] - 'a';
            rp[i][c] = {pp, c};
            a[pp++] = cc == c ? 1 : 2;
        }
        a[pp++] = 3 + c;
    }

    sa.init(a, pp, 30);
    FOR (i, 0, ll) FOR (c, 0, 26) rp[i][c].p = sa.rk[rp[i][c].p];
    rmq.init(sa.ht, pp + 1);

    FOR (i, 0, ll) {
        sort(rp[i], rp[i] + 26, [](const P& a, const P& b) {
            return a.p < b.p;
        });
        FOR (j, 0, 26) mp[i][rp[i][j].c] = j;
    }

    set<int, CMP> S;
    LL ans = 0;
    FORD (i, ll - 1, -1) {
        auto it = S.insert(i).first;
        ans += ll - i;
        if (it == S.begin()) {
            if (it != --S.end())
                ans -= lcp(i, *++it);
        } else if (it == --S.end()) {
            ans -= lcp(i, *--it);
        } else {
            auto l = it, r = it;
            --l; ++r;
            ans += lcp(*l, *r);
            ans -= lcp(i, *l) + lcp(i, *r);
        }
        printf("%lld\n", ans);
    }
}

解法 2

  • 该解法复杂度过高，肯定无法 AC。
  • 对于一个串，把它每一个字母替换成该位置和该字母上一次出现的位置之差，如果一个字母是第一次出现，那么就标记为 -1。这样就可以比较两个字符串是否同构了。
  • 和上一个解法类似，需要比较后缀字典序和求后缀 LCP。
  • 用哈希求 LCP。可以在 \(\mathrm{O}(26)\) 的时间内求出一个串的哈希值。
  • 总复杂度 \(O(26n\log^2n)\)。