洛谷 4022 「CTSC2012」熟悉的文章

发表于 | 分类于 |

也不是一道特别难的题（

建广义 SAM，对询问串的每个前缀找最长的后缀满足其为标准作文库中的子串，设这个长度为 \(l_i\)。

考虑二分 \(L\)，DP 判断。
注意到 \(i - l_i\) 不降，单调队列优化 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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1.1e6;
int n,m,q;
int L[N + 5];
char s[N + 5],t[N + 5];
int l,r,mid,ans;
namespace SAM
{
    struct node
    {
        int ch[2];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[(N << 1) + 5];
    inline void insert(int x)
    {
        if(sam[las].ch[x] && sam[las].len + 1 == sam[sam[las].ch[x]].len)
        {
            las = sam[las].ch[x];
            return ;
        }
        int cur = las,p = ++tot,flag = 0,nxt;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                cur == las && (flag = 1),nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
       las = flag ? nxt : p;
    }
}
int f[N + 5];
int check()
{
    static int q[N + 5],head,tail;
    head = 1,tail = 0,memset(f,0,sizeof(int) * mid);
    for(register int i = mid;i <= m;++i)
    {
        for(;head <= tail && f[i - mid] - i + mid > f[q[tail]] - q[tail];--tail);
        q[++tail] = i - mid;
        for(;head <= tail && q[head] < i - L[i];++head);
        f[i] = f[i - 1],head <= tail && (f[i] = max(f[i],f[q[head]] + i - q[head]));
    }
    return f[m] >= m * 0.9;
}
int main()
{
    scanf("%d%d",&q,&n);
    for(register int i = 1;i <= n;++i)
    {
        scanf("%s",s),SAM::las = 1;
        for(char *c = s;*c;SAM::insert(*c++ ^ '0'));
    }
    for(;q;--q)
    {
        scanf("%s",t + 1),m = strlen(t + 1);
        for(register int i = 1,x,p = 1,len = 0;i <= m;++i)
        {
            x = t[i] ^ '0';
            if(SAM::sam[p].ch[x])
                p = SAM::sam[p].ch[x],++len;
            else
            {
                for(;p && !SAM::sam[p].ch[x];p = SAM::sam[p].fa);
                !p ? (p = 1,len = 0) : (len = SAM::sam[p].len + 1,p = SAM::sam[p].ch[x]);
            }
            L[i] = len;
        }
        for(l = 1,r = m,ans = 0;l <= r;)
            mid = l + r >> 1,check() ? (ans = mid,l = mid + 1) : (r = mid - 1);
        printf("%d\n",ans);
    }
}