Some basic problems and introduction to Suffix Automaton

2021/02/05

Introduction:

A suffix automaton is a powerful data structure that allows solving many string-related problems.

  For example, you can search for all occurrences of one string in another, or count the amount of different substrings of a given string. Both tasks can be solved in linear time with the help of a suffix automaton.

  Intuitively a suffix automaton can be understood as a compressed form of all substrings of a given string. An impressive fact is, that the suffix automaton contains all this information in a highly compressed form.

  For a string of length \(n\) it only requires \(O(n)\) memory. Moreover, it can also be built in \(O(n)\) time (if we consider the size \(k\) of the alphabet as a constant), otherwise both the memory and the time complexity will be \(O(nlogk)\). ——CP-Algorithms

模板题:

给定一个长度为 \(n\) 的只包含小写字母的字符串 \(S\)。

对于所有 \(S\) 的出现次数不为 \(1\) 的子串,设其 \(value\) 值为该子串出现的次数 \(×\) 该子串的长度。

请计算,\(value\) 的最大值是多少。

输入格式:

共一行,包含一个由 \(n\) 个小写字母构成的字符串。

输出格式:

共一行,输出一个整数,表示答案。

数据范围:

\(1 ≤ n ≤ 10^6\),

保证至少存在一个子串出现次数大于 \(1\)。

输入样例:

aabab

输出样例:

4

思路:

直接用每个状态代表的节点的 \(endpos\) 集合大小 \(×\) 该集合的 \(longest \ value\) 更新答案即可,由于 \(parent \ tree\) 的边都是反向的,所以 \(dfs\) 的时候,要将后缀 \(link\) 边反向再搜索。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2000010; //SAM点开2倍

int tot = 1, last = 1; //从1开始
struct Node {
    int len, fa; //len就是longest最长的串的长度 fa是link的节点
    int ch[26]; //该节点的出边字母集合
} node[N];

char str[N];
ll f[N], ans; //f[i]就是节点i的endpos集合大小
int h[N], e[N], ne[N], idx; //link tree 邻接表存

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        dfs(e[i]);
        f[u] += f[e[i]]; //维护该节点的endpos
    }
    if (f[u] > 1) ans = max(ans, f[u] * node[u].len);
}

void extend(int c) {
    int p = last, np = last = ++tot;
    f[tot] = 1; //先加上前缀特殊情况
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else { //开新的点,复制
            int nq = ++tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

int main() {
    scanf("%s", &str);
    for (int i = 0; str[i]; i ++) extend(str[i] - 'a');
    memset(h, - 1, sizeof h);
    for (int i = 2; i <= tot; i++) add(node[i].fa, i); //加反向边

    dfs(1);
    printf("%lld", ans);

    return 0;
}

 

JSOI2012《玄武密码》

题目描述:

在美丽的玄武湖畔,鸡鸣寺边,鸡笼山前,有一块富饶而秀美的土地,人们唤作进香河。

相传一日,一缕紫气从天而至,只一瞬间便消失在了进香河中。

老人们说,这是玄武神灵将天书藏匿在此。

很多年后,人们终于在进香河地区发现了带有玄武密码的文字。

更加神奇的是,这份带有玄武密码的文字,与玄武湖南岸台城的结构有微妙的关联。

于是,漫长的破译工作开始了。

经过分析,我们可以用东南西北四个方向来描述台城城砖的摆放,不妨用一个长度为 \(N\) 的序列来描述,序列中的元素分别是 \(E,S,W,N\),代表了东南西北四向,我们称之为母串。

而神秘的玄武密码是由四象的图案描述而成的 \(M\) 段文字。

这里的四象,分别是东之青龙,西之白虎,南之朱雀,北之玄武,对东南西北四向相对应。

现在,考古工作者遇到了一个难题。

对于每一段文字,其前缀在母串上的最大匹配长度是多少呢?

输入格式:

第一行有两个整数,\(N\) 和 \(M\),分别表示母串的长度和文字段的个数;

第二行是一个长度为 \(N\) 的字符串,所有字符都满足是 \(E,S,W,N\) 中的一个;

之后 \(M\) 行,每行有一个字符串,描述了一段带有玄武密码的文字。依然满足,所有字符都满足是 \(E,S,W,N\) 中的一个。

输出格式:

输出有 \(M\) 行,对应 \(M\) 段文字。

每一行输出一个数,表示这一段文字的前缀与母串的最大匹配串长度。

数据范围:

\(1 ≤ N ≤ 10^7\),

\(1 ≤ M ≤ 10^5\),

保证每一段文字的长度均小于等于 \(100\)。

输入样例:

7 3
SNNSSNS
NNSS
NNN
WSEE

输出样例:

4
2
0

思路:

对于一个短串直接在母串的 \(SAM\) 暴力匹配就行,同时维护长度,直到匹配不上就停止。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 10;

int n, m;
int tot = 1, last = 1;
char str[N];// 母串

struct Node {
    int len, fa;
    int ch[4];
} node[N * 2];

inline int get(char c) {
    if (c == 'E') return 0;
    if (c == 'S') return 1;
    if (c == 'W') return 2;
    else return 3;
}

void extend(int c) {
    int p = last, np = last = ++tot;
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else {
            int nq = ++tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa)node[p].ch[c] = nq;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    scanf("%s", str);

    for (int i = 0; str[i]; i++) extend(get(str[i]));
    while (m --) {
        scanf("%s", str);
        int p = 1, res = 0;
        for (int i = 0; str[i]; i++) {
            int c = get(str[i]);
            if (node[p].ch[c]) p = node[p].ch[c], res ++;
            else break;
        }
        printf("%d\n", res);
    }

    return 0;
}

 

LOJ171《最长公共子串》

题目描述:

给定 \(n\) 个字符串,试求出这些字符串的最长公共子串。

输入格式:

第一行一个整数 \(n\)。

下面第 \(2\) 到 \(n + 1\) 行,每行一个字符串。

输出格式:

仅一行,包含一个正整数,表示 \(n\) 个字符串的最长公共子串长度。

数据范围:

\(2 ≤ n ≤ 11\),

每个字符串的长度不超过 \(10000\),

字符串均由小写字母构成。

输入样例:

2
ababc
cbaab

输出样例:

2

思路:

将第一个串作为母串建立 \(SAM\),然后用后边的所有串和该母串匹配。

开一个 \(now\) 数组,每匹配一个串,就更新一次。

每次匹配失败,就跳到 \(link\) 后缀的 \(node\) 继续匹配,然后重新计算长度。

注意每次匹配一个串之后,要 \(dfs\) 一遍,用子节点来更新 \(father\) 节点。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 20010;

int n;
int tot = 1, last = 1;
char str[N];

struct Node {
    int len, fa;
    int ch[26];
} node[N];

int ans[N], now[N]; //now是每次匹配一个串后每个节点的临时状态
int h[N], e[N], ne[N], idx;

void extend(int c) {
    int p = last, np = last = ++tot;
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++ tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        dfs(e[i]);
        now[u] = max(now[u], now[e[i]]);
    }
}

int main() {
    scanf("%d", &n);
    scanf("%s", &str); //第一个串建为SAM
    for (int i = 0; str[i]; i++) extend(str[i] - 'a');
    for (int i = 1; i <= tot; i++) ans[i] = node[i].len;
    memset(h, - 1, sizeof h);

    for (int i = 2; i <= tot; i++) add(node[i].fa, i);

    for (int i = 0; i < n - 1; i++) {
        scanf("%s", str);
        memset(now, 0, sizeof now);
        int p = 1, t = 0; //t是目前的节点longest长度
        for (int j = 0; str[j]; j++) {
            int c = str[j] - 'a';
            while (p > 1 && !node[p].ch[c]) p = node[p].fa, t = node[p].len;
            if (node[p].ch[c]) p = node[p].ch[c], t++;
            now[p] = max(now[p], t); //更新当前的每个node
        }
        dfs(1); //每个节点向其link后缀传递信息维护

        //ans存的是上一个串的每个node信息,和当前node要取min才是公共字串长度
        for (int j = 1; j <= tot; j++) ans[j] = min(ans[j], now[j]);
    }

    int res  = 0;
    for (int i = 1; i <= tot; i++) res = max(res, ans[i]); //全部匹配之后从所有node的长度取max
    printf("%d\n", res);

    return 0;
}