Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4022 [CTSC2012]熟悉的文章

Posted on In
Symbols count in article: 2.7k Reading time ≈ 2 mins.

shit，不是水题了

熟悉的文章

首先匹配的问题很好解决，SAM、SA维护文本串或者kmp处理模式串都可以

关键问题在于 $L_0$ ，首先考虑的是二分，因为答案很明显有单调性（如果长度 $L_0$ 可以，那么长度小于 $L_0$ 的也明显可以），但二分后如何判定是个问题

目测感觉和dp挂钩，有点像在kmp上dp，关键是假设已知长度为 $L_0$ ，如何得到划分方案，这边想考虑贪心

贪了一会贪不动，如果没有明显的贪心就考虑dp，设 f[i] 表示在已知长度为 $L_0$ 的情况下，以 $i$ 结尾的前缀串中“熟悉”的子串的长度总和，设以 $i$ 结尾的能匹配上的子串中最长的长度为 $len_i$ dp方程比较好推（就是状态不好设）：
$$
\begin{aligned}
f[i] = max
\begin{cases}
f[i - 1] (不让 i 成为一段) \\
f[j] + i - j, j \in [i - len_i, i - L_0] (让 i 匹配)
\end{cases}
\end{aligned}
$$
关于 $len_i$ ，可以对于每一个串预处理出来

明显可以单调队列维护，但由于数据范围是“输入文件的长度不超过 $1100000$ 字节”，所以我也不知道时间复杂度是多少

关于处理 $len_i$ ，我想的是先把文本串全都连起来（中间用 \$ 隔开），建一个SAM或者SA，然后对于每个询问直接暴力跑一遍，好像会挂

发现可以用类似AC自动机的想法，直接扫描匹配，就是建一个SAM，开始像Trie一样匹配，失配就用parent tree向上跳，大概应该也许可能是 $O(n)$ 的……吧？

还有一个实现的时候卡了的地方是单调队列维护时，区间长度是在变化的，解决办法是每次入队不是让 $i$ 入队，而是让 $i - L0$ 入队，这样可以保证队列中节点一定在区间内

结果SAM打挂了，调了好久才过样例，对这些东西还不是很熟悉啊

慢的一比的代码：

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
#include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 1.1e6 + 5;
namespace SAM
{
    int tot = 1, last = 1;
    struct Node
    {
        int len, fa;
        int ch[3];
    } nd[N << 1];
    int get_v(char ch)
    {
        return ch == '$' ? 2 : ch - '0'; 
    }
    void ins(char ch)
    {
        int x = get_v(ch);
        int p = last, np = last = ++tot;
        for (; p && !nd[p].ch[x]; p = nd[p].fa)
            nd[p].ch[x] = np;
        if (!p)
            nd[np].fa = 1;
        else
        {
            int q = nd[p].ch[x];
            if (nd[q].len == nd[p].len + 1)
                nd[np].fa = q;
            else
            {
                int nq = ++tot;
                nd[nq] = nd[q], nd[nq].len = nd[p].len + 1;
                nd[q].fa = nd[np].fa = nq;
                for (; p && nd[p].ch[x] == q; p = nd[p].fa)
                    nd[p].ch[x] = nq;
            }
        }
    }
    void find(char *s, int x[])
    {
        int p = 1, now = 0, t, len = strlen(s + 1);
        for (int i = 1; i <= len; ++i)
        {
            t = get_v(s[i]);
            if (nd[p].ch[t])
                ++now, p = nd[p].ch[t];
            else
            {
                for (; p && !nd[p].ch[t]; p = nd[p].fa);
                if (!p)
                    p = 1, now = 0;
                else
                    now = nd[p].len + 1, p = nd[p].ch[t];
            }
            x[i] = now;
        }
    }
}
int len[N];
int f[N];
bool check(int x, int sl) //x就是L0
{
    STC int q[N];
    int l = 1, r = 0;
    for (int i = 0; i < x; ++i)
        f[i] = 0;
    for (int i = x; i <= sl; ++i)
    {   
        //由于i-L0可以跟新i,所以要先入队
        while (l <= r && f[q[r]] - q[r] <= f[i - x] - (i - x))
            --r;
        q[++r] = i - x;
        f[i] = f[i - 1];
        while (l <= r && q[l] < i - len[i])
            ++l;
        if (l <= r)
            f[i] = max(f[i], f[q[l]] + i - q[l]);    
    }
    return f[sl] * 10 >= sl * 9;
}
int work(char *s)
{
    SAM::find(s, len);
    int sl = strlen(s + 1);
    int l = 0, r = sl, mid, res = 0;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (check(mid, sl))
        {
            res = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return res;
}
int main()
{
    int n, m;
    STC char s[N];
    scanf("%d%d", &n, &m);
    for (int i = 1, t; i <= m; ++i)
    {
        scanf("%s", s + 1);
        t = strlen(s + 1);
        for (int j = 1; j <= t; ++j)
            SAM::ins(s[j]);
        SAM::ins('$');
    }
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", s + 1);
        printf("%d\n", work(s));
    }
    return 0;
}