Chaos Slover 补档计划 - 字符串基本算法

2015.11.19 09:39 Thu| 12 visits oi_2016| ChaosSlover补档计划| Text

Manacher 算法

BZOJ2160 拉拉队排练

Manacher,预处理出多大的和谐小群体分别有多少个,然后贪心选 K 次就好了。而且这道题不需要分隔符……

其实这题不特判 -1 也能 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
#include <bits/stdc++.h>
using namespace std;

#define N 1000005
#define mod 19930726

char str[N];
int n, p[N], cnt[N];
long long ans = 1, m;

long long power(long long a, long long b)
{
    long long re = 1;
    while (b)
    {
        if (b & 1) re = (re * a) % mod;
        a = (a * a) % mod, b >>= 1;
    }
    return re;
}

void manacher(char str[], int len)
{
    str[0] = '$';
    int maxp = 0, id = 0;
    for (int i = 1; i <= len; ++i)
    {
        if (maxp > i) p[i] = min(p[id * 2 - i], maxp - i);
        else p[i] = 1;
        while (str[i - p[i]] == str[i + p[i]]) ++p[i];
        if (i + p[i] > maxp) maxp = i + p[i], id = i;
    }
    for (int i = 1; i <= len; ++i)
        ++cnt[p[i]];
    for (int i = len - 1; i; --i)
        cnt[i] += cnt[i + 1];
}

int main()
{
    cin >> n >> m;
    scanf("%s", str + 1);
    manacher(str, n);
    for (int i = n; i; --i)
    {
        if (m > cnt[i])
            ans = (ans * power(i * 2 - 1, cnt[i])) % mod, m -= cnt[i];
        else
            ans = (ans * power(i * 2 - 1, m)) % mod, m = 0;
        if (m == 0) break;
    }
    if (m) puts("-1");
    else cout << ans << endl;
    return 0;
}

BZOJ2342 [Shoi2011]双倍回文

这一道题写完之后能编译了就直接 AC 了……

首先还是要用 Manacher 算法求出每一个点能够扩展的长度。然后枚举总的对称轴 i,发现能够更新答案的左半边对称轴 j 满足 i-p[i]/2<=j<i 且 j+p[j]>=i。发现一个左对称轴 j 有可能更新在 j+1 到 j+p[j] 这一段区间中的对称轴的答案,因此就可以记录它的出现时间和删除时间,用 set 维护。从左向右依次枚举对称轴,查询总对称轴 i 时二分查找当前的 set 中不小于 i-p[i]/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
#include <bits/stdc++.h>
using namespace std;

#define N 500005

int n, p[N * 2];
char str[N], s[N * 2];
set<int> st;
vector<int> del[N];

void manacher(char str[], int len)
{
    s[0] = '$'; s[1] = '#';
    for  (int i = 0; i < len; ++i)
        s[i * 2 + 2] = str[i], s[i * 2 + 3] = '#';
    len = len * 2 + 2;
    int maxp = 0, id = 0;
    for (int i = 1; i <= len; ++i)
    {
        if (maxp > i) p[i] = min(p[id * 2 - i], maxp - i);
        else p[i] = 1;
        while (s[i - p[i]] == s[i + p[i]]) ++p[i];
        if (i + p[i] > maxp) maxp = i + p[i], id = i;
    }
    for (int i = 1; i < len; i += 2)
        p[i >> 1] = (p[i] - 1) / 2;
}

int main()
{
    cin >> n;
    scanf("%s", str);
    manacher(str, n);
    int ans = 0;
    for (int i = 1; i < n; ++i)
    {
        if (st.lower_bound(i - p[i] / 2) != st.end())
            ans = max(ans, i - *st.lower_bound(i - p[i] / 2));
        st.insert(i); del[i + p[i]].push_back(i);
        for (int j = 0; j < (int)del[i].size(); ++j)
            st.erase(del[i][j]);
    }
    cout << ans * 4 << endl;
    return 0;
}

KMP 算法

BZOJ1355 [Baltic2009]Radio Transmission

之前已经把 KMP 算法忘光了的我……由于 pre 数组的性质,str[1...pre[n]]=str[n-pre[n]+1...n]。然后就可以发现循环节是 n-pre[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
#include <bits/stdc++.h>
using namespace std;

#define N 1000005

int n, pre[N]; char a[N];

void getpre(char str[], int len)
{
    int fix = 0;
    for (int i = 2; i <= len; ++i)
    {
        while (fix && str[fix + 1] != str[i])
            fix = pre[fix];
        if (str[fix + 1] == str[i]) ++fix;
        pre[i] = fix;
    }
}

int main()
{
    cin >> n;
    scanf("%s", a + 1);
    getpre(a, n);
    cout << n - pre[n] << endl;
    return 0;
}

BZOJ3670 [Noi2014]动物园

将 pre 数组看成父亲边构成的树结构称为 KMP 的 fail 树,0 号点为根。

性质 1:结点 i 到根的链上的所有点,是满足 Next 性质的所有串。

性质 2:字符串 S[1~m] 在串 S 中出现的所有位置为 m 子树中的点。

然后对于这道题,我们要求的就是对于每一个结点 i,在 fail 树上找一个深度最大的结点 j,使得 j<=i/2,然后将它的深度计入答案。类似于 KMP 地再扫一遍。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 1000005
#define mod 1000000007

int n, fix, pre[N], cnt[N];
char str[N];
long long ans = 1;

void kmp(char str[])
{
    int fix = 0;
    cnt[1] = 1;
    for (int i = 2; str[i]; ++i)
    {
        while (fix && str[fix + 1] != str[i])
            fix = pre[fix];
        if (str[fix + 1] == str[i]) ++fix;
        pre[i] = fix; cnt[i] = cnt[fix] + 1;
    }
    fix = 0; ans = 1;
    for (int i = 2; str[i]; ++i)
    {
        while (fix && str[fix + 1] != str[i])
            fix = pre[fix];
        if (str[fix + 1] == str[i]) ++fix;
        while (fix > i / 2) fix = pre[fix];
        ans = ans * (cnt[fix] + 1) % mod;
    }
}

int main()
{
    cin >> n;
    while (n--)
    {
        scanf("%s", str + 1);
        kmp(str);
        cout << ans << endl;
    }
}

Trie 树

BZOJ1174 [Balkan2007]Toponyms

妈妈问我为何精神恍惚……

Warning:这显然是一道傻题,然而网上的题解全都是 RE 的!包括 HZWER 他们……

然而,在 google 上的一个角落找到了 VFK 大神的题解,发现这个是用指针指向自己的一个孩子,然后每一个孩子指向自己的兄弟。这样可以压缩内存……QY 是要有多神啊,这种题还往 PPT 里面放。

 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
#include <bits/stdc++.h>
using namespace std;

int n;
char str[1000005];
long long ans = 0;

struct node
{
    int cnt; char val;
    node *son, *bro;
    node(char _val = 0) : cnt(0), val(_val), son(0), bro(0) {}
    void *operator new(size_t s);
} newnode[6000005], *pos = newnode;

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

node *root = new node();

node *getson(node *x, char c)
{
    if (x->val == c || !x->bro) return x;
    return getson(x->bro, c);
}

void insert(char str[])
{
    node *p = root;
    for (int i = 0; str[i]; ++i)
    {
        if (!p->son) p->son = new node(str[i]);
        p = getson(p->son, str[i]);
        if (p->val != str[i])
            p->bro = new node(str[i]), p = p->bro;
        ans = max(ans, 1ll * (++p->cnt) * (i + 1));
    }
}

int main()
{
    cin >> n; getchar();
    while (n--)
        gets(str), insert(str);
    cout << ans << endl;
    return 0;
}

BZOJ1954 Pku3764 The xor-longest Path

求树上异或值最长的路径。预处理出所有点到根结点的异或距离,然后选定路径的两个端点,那么它们之间的异或距离就是这两个端点到根的距离的异或值。这样,可以用 trie 树贪心,对于每一个结点找到以它为一端点的路径最长值就好了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 100005

struct node
{
    node *son[2];
};

node *root = new node();
int n, ans, head[N], val[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void insert(int t)
{
    node *p = root;
    for (int i = 30; i >= 0; --i)
    {
        int c = (t >> i) & 1;
        if (!p->son[c])
            p->son[c] = new node();
        p = p->son[c];
    }
}

int query(int t)
{
    node *p = root;
    int re = 0;
    for (int i = 30; i >= 0; --i)
    {
        int c = (t >> i) & 1;
        if (!p->son[c ^ 1])
            p = p->son[c];
        else re ^= 1 << i, p = p->son[c ^ 1];
    }
    return re;
}

void dfs(int x, int fa)
{
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa)
            val[edge[i].to] = val[x] ^ edge[i].val,
            dfs(edge[i].to, x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int x, y, z, i = 1; i < n; ++i)
        cin >> x >> y >> z, add(x, y, z), add(y, x, z);
    dfs(1, 0);
    insert(0);
    for (int i = 2; i <= n; ++i)
    {
        ans = max(ans, query(val[i]));
        insert(val[i]);
    }
    cout << ans << endl;
    return 0;
}

AC 自动机&Trie 图

BZOJ2938 [Poi2000]病毒

查询是否存在无限长的不含病毒的字符串,相当于询问 Trie 图中是否含有一个环,用 DFS 扫一遍判断就好了。注意如果结点 x 表示病毒,那么 pre 指针指向 x 的结点也都含有病毒,需要在建立 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
#include <bits/stdc++.h>
using namespace std;

struct trie
{
    struct node
    {
        node *son[2], *pre;
        int len;
        bool ins, vis, end;
        node(int _len = 0) : len(_len), ins(0), vis(0), end(0)
        { memset(son, 0, sizeof son); pre = 0; }
    };

    node *root;

    trie() { root = new node(); }

    void insert(char str[])
    {
        node *p = root;
        while (*str)
        {
            if (!p->son[*str - '0'])
                p->son[*str - '0'] = new node(p->len + 1);
            p = p->son[*str - '0']; ++str;
        }
        p->end = true;
    }

    void build_ac()
    {
        queue<node *> q;
        root->pre = root;
        for (int i = 0; i < 2; ++i)
            if (!root->son[i]) root->son[i] = root;
            else root->son[i]->pre = root, q.push(root->son[i]);
        while (!q.empty())
        {
            node *t = q.front(); q.pop();
            t->end |= t->pre->end;
            for (int i = 0; i < 2; ++i)
                if (!t->son[i]) t->son[i] = t->pre->son[i];
                else t->son[i]->pre = t->pre->son[i], q.push(t->son[i]);
        }
    }

    bool dfs(node *p)
    {
        p->ins = 1;
        for (int i = 0; i < 2; ++i)
        {
            if (p->son[i]->ins) return true;
            if (p->son[i]->vis || p->son[i]->end) continue;
            p->son[i]->vis = 1;
            if (dfs(p->son[i])) return true;
        }
        p->ins = 0;
        return false;
    }
};

trie t;
int n; char str[30005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%s", str), t.insert(str);
    t.build_ac();
    if (t.dfs(t.root)) puts("TAK");
    else puts("NIE");
    return 0;
}

BZOJ1030 [JSOI2007]文本生成器

trie 图 + DP。和上一道题一样,需要判断每一个结点是否包含单词。在 trie 图上 DP,求出不可读的文本数,然后用总数减去就好了。

  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
#include <bits/stdc++.h>
using namespace std;

#define mod 10007

struct trie
{
    struct node
    {
        node *son[26], *pre;
        int len, vis; short f[10005];
        bool end;
        node(int _len = 0) : len(_len), vis(-1), end(0)
        {
            memset(son, 0, sizeof son); pre = 0;
            memset(f, 0, sizeof f);
        }
    };

    node *root;

    trie() { root = new node(); }

    void insert(char str[])
    {
        node *p = root;
        while (*str)
        {
            if (!p->son[*str - 'A'])
                p->son[*str - 'A'] = new node(p->len + 1);
            p = p->son[*str - 'A']; ++str;
        }
        p->end = true;
    }

    void build_ac()
    {
        queue<node *> q;
        root->pre = root;
        for (int i = 0; i < 26; ++i)
            if (!root->son[i]) root->son[i] = root;
            else root->son[i]->pre = root, q.push(root->son[i]);
        while (!q.empty())
        {
            node *t = q.front(); q.pop();
            t->end |= t->pre->end;
            for (int i = 0; i < 26; ++i)
                if (!t->son[i]) t->son[i] = t->pre->son[i];
                else t->son[i]->pre = t->pre->son[i], q.push(t->son[i]);
        }
    }

    void dfs(node *p, int t)
    {
        p->vis = t;
        for (int i = 0; i < 26; ++i)
        {
            p->son[i]->f[t + 1] += p->f[t],
            p->son[i]->f[t + 1] %= mod;
            if (!p->son[i]->end && p->son[i]->vis != t)
                dfs(p->son[i], t);
        }
    }

    int ans(node *p, int t)
    {
        p->vis = t;
        int re = p->f[t];
        for (int i = 0; i < 26; ++i)
            if (!p->son[i]->end && p->son[i]->vis != t)
                re += ans(p->son[i], t);
        return re % mod;
    }
};

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = (re * a) % mod;
        a = a * a % mod; b >>= 1;
    }
    return re;
}

trie t;
int n, m; char str[105];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        scanf("%s", str), t.insert(str);
    t.build_ac();
    t.root->f[0] = 1;
    for (int i = 0; i < m; ++i)
        t.dfs(t.root, i);
    cout << (power(26, m) - t.ans(t.root, m) + mod) % mod << endl;
    return 0;
}

BZOJ3251&2462 [BeiJing2011]矩阵模板

据说是一道 hash 的好题……这两道题虽然是双倍经验,但数据强度不可同日而语(1s+ VS 15s+)!

CY 大神在 PPT 上说这是一道二维 AC 自动机,结果吓到我了。实际上,这并不是 AC 自动机在二维上的推广什么的很高级的东西。

不幸的是,在网上基本看不到这道题的 AC 自动机题解的,可以参见 Uva11019 的题解。

设原矩阵为 mat,询问矩阵为 str。将它们都拆成一行一行的形式,对矩阵 str 中的 a 个串建立 AC 自动机,将原矩阵中的每一行到自动机中匹配。如果发现 mat[id][j..j+b]=str[i],那么就说明原矩阵中以 (id-i+1, j+b) 为右上角,与 str 大小相同的子矩阵的第 i 行和 str[i] 相同。如果最后发现原矩阵中以某一个点为右上角的子矩阵的每一行都和 str 相同(cnt 值为 a),那么就有解。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n, m, a, b, q, ans[N][N];
char mat[N][N], str[N][N];

struct node
{
    node *son[2], *pre;
    vector<int> v;
    node() : pre(0)
    {
        son[0] = son[1] = 0; v.resize(0);
    }
    void *operator new(size_t s);
} newnode[N * N], *pos;

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

node *root;

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

void insert(int id, char str[])
{
    node *p = root;
    while (*str)
    {
        if (!p->son[*str - '0'])
            p->son[*str - '0'] = new node();
        p = p->son[*str - '0']; ++str;
    }
    p->v.push_back(id);
}

void build_ac()
{
    queue<node *> q;
    root->pre = root;
    for (int i = 0; i < 2; ++i)
        if (!root->son[i]) root->son[i] = root;
        else root->son[i]->pre = root, q.push(root->son[i]);
    while (!q.empty())
    {
        node *t = q.front(); q.pop();
        for (int i = 0; i < 2; ++i)
            if (!t->son[i]) t->son[i] = t->pre->son[i];
            else t->son[i]->pre = t->pre->son[i], q.push(t->son[i]);
    }
}

void query(int id, char str[])
{
    node *p = root;
    for (int i = 0; str[i]; ++i)
    {
        p = p->son[str[i] - '0'];
        for (int j = 0; j < (int)p->v.size(); ++j)
            ++ans[i][id - p->v[j]];
    }
}

int main()
{
    cin >> m >> n >> a >> b;
    for (int i = 1; i <= m; ++i)
        scanf("%s", mat[i]);
    cin >> q;
    while (q--)
    {
        reset();
        for (int i = 1; i <= a; ++i)
            scanf("%s", str[i]), insert(i, str[i]);
        build_ac();
        memset(ans, 0, sizeof ans);
        for (int i = 1; i <= m; ++i)
            query(i, mat[i]);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (ans[i][j] == a)
                    { puts("1"); goto end; }
        puts("0");
        end: ;
    }
    return 0;
}

HDU3992 Crazy Typewriter

题意:打字机疯掉了,每一次有一定概率打出一个字母。问期望打多少字母后能够得到某个目标串。

首先还是建出来 Trie 图,然后算期望。显然终点的期望是 0。然后就可以列出来一大堆方程,高斯消元求解,输出 f[0][tot]。

怎么判断 inf 呢?

第一种方式:判断字母的概率是否为 0 什么的,很简单。

第二种方式:随便输入一组无解的数据,发现求出的是 nan。(为什么求出的不是 inf 呢?)然后用 isnan() 函数判断就好了。正确性我不知道……

  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
#include <bits/stdc++.h>
using namespace std;

#define N 300

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

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

node *root;
int n, tot;
double p[30], f[N][N];
char str[30];

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

void insert(char str[])
{
    node *p = root;
    while (*str)
    {
        if (!p->son[*str - 'a'])
            p->son[*str - 'a'] = new node(p->len + 1);
        p = p->son[*str - 'a']; ++str;
    }
    p->end = true;
}

void build_ac()
{
    queue<node *> q;
    root->pre = root;
    for (int i = 0; i < 26; ++i)
        if (!root->son[i]) root->son[i] = root;
        else root->son[i]->pre = root, q.push(root->son[i]);
    while (!q.empty())
    {
        node *t = q.front(); q.pop();
        t->end |= t->pre->end;
        for (int i = 0; i < 26; ++i)
            if (!t->son[i]) t->son[i] = t->pre->son[i];
            else t->son[i]->pre = t->pre->son[i], q.push(t->son[i]);
    }
}

void gauss()
{
    for (int i = 0; i < tot; ++i)
    {
        int t = i;
        for (int j = i; j < tot; ++j)
            if (fabs(f[j][i]) > 1e-5)
                { t = j; break; }
        if (t != i)
            for (int j = 0; j <= tot; ++j)
                swap(f[i][j], f[t][j]);
        for (int j = i + 1; j < tot; ++j)
        {
            if (f[j][i] == 0) continue;
            double d = f[j][i] / f[i][i];
            for (int k = i; k <= tot; ++k)
                f[j][k] -= f[i][k] * d;
        }
    }
    for (int i = tot - 1; i >= 0; --i)
    {
        f[i][tot] /= f[i][i];
        for (int j = i - 1; j >= 0; --j)
            f[j][tot] -= f[i][tot] * f[j][i];
    }
}

int main()
{
    while (cin >> n)
    {
        for (int i = 0; i < 26; ++i)
            cin >> p[i];
        reset();
        for (int i = 1; i <= n; ++i)
            scanf("%s", str), insert(str);
        build_ac();
        tot = pos - trie;
        memset(f, 0, sizeof f);
        for (int i = 0; i < tot; ++i)
            if (trie[i].end) f[i][i] = 1, f[i][tot] = 0;
            else
            {
                f[i][i] = -1, f[i][tot] = -1;
                for (int j = 0; j < 26; ++j)
                    f[i][trie[i].son[j] - trie] += p[j];
            }
        gauss();
        if (isnan(f[0][tot])) puts("Infinity");
        else
            cout << fixed << setprecision(6) << f[0][tot] << endl;
    }
    return 0;
}