Chaos Slover 补档计划 - 后缀自动机(1)

2015.11.16 11:18 Mon| 53 visits oi_2016| ChaosSlover补档计划| Text

后缀自动机

努力了好久终于有一点点开窍了……

今天 wzq 联赛考挂退役了,祝他在什么地方都能焕发光彩吧。竞赛大概是一条孤独的路,充满着各种不确定性。然而我既然选择了它,也就要努力地走好这条路吧。无论结果怎样,只愿不留遗憾。

POJ1509 Glass Beads

最小表示法裸题,昨天刚刚学过。然而也是一道后缀树裸题,CLJ 的 PPT 第一道例题。

将原串复制两次后放进后缀自动机里面去,然后从根开始贪心向最左边的子结点走 L 次,就是原串的循环最小表示。

然而需要注意的是,如果每一次不删干净后缀树,会 MLE。然而后缀自动机是一张拓扑图,直接遍历删除会很令人困扰……

考虑重载结点的结构体中的 new 函数,然而我在学了半天语法之后决定再也不把后缀自动机封装到结构体里面了,就像上周尝试封装可持久化线段树一样。为什么我在这种奇怪的地方总失败 T^T

 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

struct node
{
    int pos, len;
    node *son[26], *pre;
    node(int _len = 0) : len(_len)
    {
        memset(son, 0, sizeof son); pre = 0;
    }
    void *operator new(size_t s);
} newnode[40005], *p;

void *node::operator new(size_t s)
{
    return p++;
}

node *root, *last;

void insert(int c)
{
    node *p = last, *np = new node(p->len + 1);
    while (p && p->son[c] == NULL)
        p->son[c] = np, p = p->pre;
    if (!p) np->pre = root;
    else
    {
        node *q = p->son[c];
        if (q->len == p->len + 1)
            np->pre = q;
        else
        {
            node *nq = new node(p->len + 1);
            memcpy(nq->son, q->son, sizeof nq->son);
            nq->pre = q->pre;
            np->pre = q->pre = nq;
            while (p && p->son[c] == q)
                p->son[c] = nq, p = p->pre;
        }
    }
    last = np;
}

int get(int n)
{
    node *p = root;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < 26; ++j)
            if (p->son[j])
                { p = p->son[j]; break; }
    return p->len;
}

void reset()
{
    p = newnode;
    last = root = new node();
}


int t, n;
char str[10005];

int main()
{
    cin >> t;
    while (t--)
    {
        scanf("%s", str);
        n = strlen(str);
        reset();
        for (int i = 0; i < n; ++i)
            insert(str[i] - 'a');
        for (int i = 0; i < n; ++i)
            insert(str[i] - 'a');
        cout << get(n) - n + 1 << endl;
    }
    return 0;
}

SPOJNSUBSTR Substrings

CLJ 课件里面的第二道例题。

对于一个结点 s,它的出现次数是 |right(s)|,因此用 |right(s)| 去更新 ans[len(s)]。由于一个结点出现的范围是 [len(s->pre)+1,len(s)],因此最后要用 ans[i+1] 更新 ans[i]。由于 ans[i] 一定不小于 ans[i+1],因此不会出现错误。

关键就在于如何求 right 了。这就需要拓扑排序啦。先把 father 树上所有叶子结点的 right 设成 1,然后按照 len 从大到小的顺序更新。

注意这里只能够乖乖地写拓扑排序,不能妄想用 DFS 解决……

如果不写基数排序,可以尝试一下 vector。SPOJ 有 C++14,好评。

 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, ans[250005];
char str[250005];

struct node
{
    int len, vis, right;
    node *son[26], *pre;
    node(int _len = 0) : len(_len)
    {
        memset(son, 0, sizeof son); pre = 0;
    }
    void *operator new(size_t s);
} newnode[500005], *p;
vector<node *> v[250005];

void *node::operator new(size_t s)
{
    return p++;
}

node *root, *last;

void insert(int c)
{
    node *p = last, *np = new node(p->len + 1);
    while (p && p->son[c] == NULL)
        p->son[c] = np, p = p->pre;
    if (!p) np->pre = root;
    else
    {
        node *q = p->son[c];
        if (q->len == p->len + 1)
            np->pre = q;
        else
        {
            node *nq = new node(p->len + 1);
            memcpy(nq->son, q->son, sizeof nq->son);
            nq->pre = q->pre;
            np->pre = q->pre = nq;
            while (p && p->son[c] == q)
                p->son[c] = nq, p = p->pre;
        }
    }
    last = np;
}

void reset()
{
    p = newnode;
    last = root = new node();
}

void getright(char str[], int len)
{
    node *p = root;
    for (int i = 0; i < len; ++i)
        p = p->son[*str - 'a'], ++p->right, ++str;
}

int main()
{
    scanf("%s", str);
    n = strlen(str);
    reset();
    for (int i = 0; i < n; ++i)
        insert(str[i] - 'a');
    getright(str, n);
    for (node *i = newnode; i < p; ++i)
        v[i->len].push_back(i);
    for (int i = n; i; --i)
        for (auto j : v[i])
            ans[i] = max(ans[i], j->right),
            j->pre->right += j->right;
    for (int i = n - 1; i; --i)
        ans[i] = max(ans[i], ans[i + 1]);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

SPOJSUBLEX Lexicographical Substring Search

CLJ 课件的第四题,第三题是动态树维护 right 数组,刷不动了 T^T。

开始的时候由于对 right 理解不深,所以算法错了……

right 表示的是从这个结点开始能够得到的后缀,它的大小也就可以表示字符串出现的次数了。而求不同子串个数的话,对于一个结点需要从它能够转移到的更长子串通过递推得到。同样需要拓扑排序。

【听说 SPOJ 卡常数,所以我们需要预先记录下来每一个结点能够转移到的非空结点,从而优化常数。然而 SPOJ 不卡 STL 好评。】

 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, q, k;
char str[90005];

struct node
{
    int len, vis, sum;
    node *son[26], *pre;
    node(int _len = 0) : len(_len)
    {
        memset(son, 0, sizeof son); pre = 0;
    }
    void *operator new(size_t s);
} newnode[180005], *pos;

void *node::operator new(size_t s)
{
    return pos++;
}

node *root, *last;
vector<node *> v[90005];
vector<pair<node *, int> > to[180005];

void insert(int c)
{
    node *p = last, *np = new node(p->len + 1);
    while (p && p->son[c] == NULL)
        p->son[c] = np, p = p->pre;
    if (!p) np->pre = root;
    else
    {
        node *q = p->son[c];
        if (q->len == p->len + 1)
            np->pre = q;
        else
        {
            node *nq = new node(p->len + 1);
            memcpy(nq->son, q->son, sizeof nq->son);
            nq->pre = q->pre;
            np->pre = q->pre = nq;
            while (p && p->son[c] == q)
                p->son[c] = nq, p = p->pre;
        }
    }
    last = np;
}

void reset()
{
    pos = newnode;
    last = root = new node();
}

void getsum(char str[], int len)
{
    for (node *i = newnode; i < pos; ++i)
        i->sum = 1, v[i->len].push_back(i);
    for (int i = n; i >= 0; --i)
        for (auto j : v[i])
            for (int k = 0; k < 26; ++k)
                if (j->son[k])
                    to[j - newnode].push_back(make_pair(j->son[k], k)),
                    j->sum += j->son[k]->sum;
}

void dfs(node *p, int k)
{
    if (--k == 0) return;
    for (auto i : to[p - newnode])
    {
        if (i.first->sum < k) k -= i.first->sum;
        else { putchar('a' + i.second), dfs(i.first, k); break; }
    }
}

int main()
{
    scanf("%s", str);
    n = strlen(str);
    reset();
    for (int i = 0; i < n; ++i)
        insert(str[i] - 'a');
    getsum(str, n);
    cin >> q;
    for (int i = 1; i <= q; ++i, puts(""))
        cin >> k, dfs(root, k + 1);
    return 0;
}

SPOJLCS Longest Common Substring

CLJ 课件的第五道例题。首先对于 A 串构造 SAM,然后将 B 串在 A 串上面匹配。就像 AC 自动机一样,如果匹配不上就顺着 pre 指针往上跳,用当前匹配的长度更新答案。

然而发现在 SAM 中,一个结点所代表的是一段不同长度的子串区间,因此不能直接用当前匹配到结点的 len 去更新答案。

考虑如果按照 pre 指针向上跳,假设我们之前匹配到了自动机中的 p 结点。由于我们之前可能已经匹配了很长一段区间了,而且匹配的区间长度不小于 min(p)=max(p->pre)+1=len(p->pre)+1,因此向上跳的时候长度值只需要减小到 len(p->pre),即结点 p->pre 能够表示的最长子串长度即可。

经过上述操作之后,就能够从当前结点开始继续匹配了,将 len+1 并更新答案。

当然,如果直到跳到了 root 也没有能向下走的边,就说明当前 B 串中的字符压根没在 A 串里面出现过,直接将 len 设为 0,重新从 root 开始匹配吧。

 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, q, k;
char str[250005];

struct node
{
    int len, vis, sum;
    node *son[26], *pre;
    node(int _len = 0) : len(_len)
    {
        memset(son, 0, sizeof son); pre = 0;
    }
    void *operator new(size_t s);
} newnode[500005], *pos;

void *node::operator new(size_t s)
{
    return pos++;
}

node *root, *last;

void insert(int c)
{
    node *p = last, *np = new node(p->len + 1);
    while (p && p->son[c] == NULL)
        p->son[c] = np, p = p->pre;
    if (!p) np->pre = root;
    else
    {
        node *q = p->son[c];
        if (q->len == p->len + 1)
            np->pre = q;
        else
        {
            node *nq = new node(p->len + 1);
            memcpy(nq->son, q->son, sizeof nq->son);
            nq->pre = q->pre;
            np->pre = q->pre = nq;
            while (p && p->son[c] == q)
                p->son[c] = nq, p = p->pre;
        }
    }
    last = np;
}

void reset()
{
    pos = newnode;
    last = root = new node();
}

int getans(char str[], int len)
{
    node *p = root;
    int re = 0, now = 0;
    for (int i = 0; i < len; ++i)
    {
        if (p->son[str[i] - 'a']) ++now, p = p->son[str[i] - 'a'];
        else
        {
            while (p && !p->son[str[i] - 'a']) p = p->pre;
            if (!p) now = 0, p = root;
            else now = p->len + 1, p = p->son[str[i] - 'a'];
        }
        re = max(re, now);
    }
    return re;
}

int main()
{
    scanf("%s", str);
    n = strlen(str);
    reset();
    for (int i = 0; i < n; ++i)
        insert(str[i] - 'a');
    scanf("%s", str);
    n = strlen(str);
    cout << getans(str, n) << endl;
    return 0;
}

SPOJLCS2 Longest Common Substring II

求多个串的最长公共子串长度。和上一道题基本相同。

依次加入每一个串,在更新答案时,对于同一个串,在每一个结点上保存匹配长度的最大值。再遍历一遍,更新所有串在每一个结点上的匹配长度的最小值,其中的最大值就是对于当前串的答案。

需要注意的点:

  • 计算结点 p 上的答案时,不要忘记更新 p->pre 的答案为 p->pre->len。
  • 最开始结点 p 上的答案是有初始值的,即 p->len。 另外我真的不知道为什么 top[i]->pre->ans1 = max(top[i]->ans1, top[i]->pre->ans1); 这一句话不这么写就一定会 TLE #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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, n1;
char str[100005];

struct node
{
    int len, ans, ans1;
    node *son[26], *pre;
    node(int _len = 0) : len(_len), ans(_len), ans1(0)
    {
        memset(son, 0, sizeof son); pre = 0;
    }
    void *operator new(size_t s);
} newnode[200005], *pos;

void *node::operator new(size_t s)
{
    return pos++;
}

node *root, *last;
vector<node *> v[100005];
node *top[200005]; int tot;

void insert(int c)
{
    node *p = last, *np = new node(p->len + 1);
    while (p && p->son[c] == NULL)
        p->son[c] = np, p = p->pre;
    if (!p) np->pre = root;
    else
    {
        node *q = p->son[c];
        if (q->len == p->len + 1)
            np->pre = q;
        else
        {
            node *nq = new node(p->len + 1);
            memcpy(nq->son, q->son, sizeof nq->son);
            nq->pre = q->pre;
            np->pre = q->pre = nq;
            while (p && p->son[c] == q)
                p->son[c] = nq, p = p->pre;
        }
    }
    last = np;
}

void reset()
{
    pos = newnode;
    last = root = new node();
}

void topsort()
{
    for (node *i = newnode; i != pos; ++i)
        v[i->len].push_back(i);
    for (int i = 0; i <= n; ++i)
        for (auto j : v[i])
            top[tot++] = j;
}

int getans(char str[], int len)
{
    node *p = root;
    int re = 0, now = 0;
    for (int i = 0; i < len; ++i)
    {
        if (p->son[str[i] - 'a']) ++now, p = p->son[str[i] - 'a'];
        else
        {
            while (p && !p->son[str[i] - 'a']) p = p->pre;
            if (!p) now = 0, p = root;
            else now = p->len + 1, p = p->son[str[i] - 'a'];
        }
        p->ans1 = max(p->ans1, now);
    }
    for (int i = tot - 1; i >= 1; --i)
    {
        top[i]->ans = min(top[i]->ans, top[i]->ans1);
        top[i]->pre->ans1 = max(top[i]->ans1, top[i]->pre->ans1);
        top[i]->ans1 = 0; re = max(re, top[i]->ans);
    }
    return re;
}

int main()
{
    scanf("%s", str);
    n = strlen(str);
    reset();
    for (int i = 0; i < n; ++i)
        insert(str[i] - 'a');
    topsort();
    int ans = n;
    while (scanf("%s", str) != EOF)
    {
        int n1 = strlen(str);
        ans = getans(str, n1);
    }
    cout << ans << endl;
    return 0;
}