P4022 [CTSC2012]熟悉的文章

发表于 | 阅读数

有多个主串,每次询问将询问串分成多个连续子串,如果一个子串长度$\ge L$且在主串中出现过就是合法的

如果合法的子串总长度$\ge$询问串长的$90\%$%,这个串就是合法的字符串,求使得询问串成为合法的字符串的最大的$L$

$L$具有单调性。考虑二分答案。即使得子串长度$\geq L$，使得合法的长度尽可能得大。

考虑$dp[i]$为$[1,i]$中含有合法子串最长长度。

$maxlen_i$表示从询问串第$i$位最多能往后匹配多长。可以预处理出来。

考虑$i-maxlen_i$，不严格递增。单调队列维护窗口最大值即可。

代码 
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

const int SN = 2e6 + 10;
const int SM = 2;

struct SAM
{
    int trans[SN][SM];
    int mxl[SN], link[SN], pre, scnt;
    SAM() { pre = scnt = 1; };
    void init()
    {
        for (int j = 1; j <= scnt; j++)
        {
            link[j] = 0;
            mxl[j] = 0;
            //siz[j] = 0;
            memset(trans[j], 0, sizeof(trans[j]));
        }
        scnt = pre = 1;
    };
    void insert(int id)
    {
        int cur = ++scnt;
        mxl[cur] = mxl[pre] + 1;
        int u;

        for (u = pre; u && !trans[u][id]; u = link[u])
            trans[u][id] = cur;
        pre = cur;
        if (!u)
            link[cur] = 1;
        else
        {
            int x = trans[u][id];
            if (mxl[x] == mxl[u] + 1)
                link[cur] = x;
            else
            {
                int nc = ++scnt;
                link[nc] = link[x];
                mxl[nc] = mxl[u] + 1;
                memcpy(trans[nc], trans[x], sizeof(trans[x]));

                link[cur] = link[x] = nc;
                for (; u && trans[u][id] == x; u = link[u])
                    trans[u][id] = nc;
            }
        }
    }
} sam;
int pmx[SN];
void prepare(char *t)
{
    int len = strlen(t + 1);
    int u = 1, lc = 0;
    for (int i = 1; i <= len; i++)
    {
        int id = t[i] - '0';
        while (u && !sam.trans[u][id])
            u = sam.link[u], lc = sam.mxl[u];
        if (sam.trans[u][id])
            u = sam.trans[u][id], lc++;
        else
            u = 1, lc = 0;
        pmx[i] = lc;
        //cout << lc;
    }
}
int dp[SN];
bool check(char *t, int L)
{
    deque<int> q;
    int len = strlen(t + 1);

    for (int i = 0; i <= len; i++)
        dp[i] = 0;
    for (int i = L; i <= len; i++)
    {
        dp[i] = dp[i - 1];
        while (!q.empty() && dp[q.back()] - q.back() < dp[i - L] - (i - L))
            q.pop_back();
        q.push_back(i - L);
        //cout << i - pmx[i] << " " << i - L << " ";
        while (!q.empty() && q.front() < i - pmx[i])
            q.pop_front();
        if (q.size())
            dp[i] = max(dp[i], dp[q.front()] - q.front() + i);
        //cout << dp[i] << " " << endl;
        ;
    }
    return dp[len] * 10 >= len * 9;
}
char t[SN];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%s", t + 1);
        int len = strlen(t + 1);
        sam.pre = 1;
        for (int j = 1; j <= len; j++)
            sam.insert(t[j] - '0');
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", t + 1);
        prepare(t);
        int l = 0, r = strlen(t + 1);
        int ans = 0;
        //cout << check(t, 4) << endl;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (check(t, mid))
            {
                ans = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        printf("%d\n", ans);
    }
}