Blackops

初心易得，始终难守

0%

CF 873F Forbidden Indices（后缀自动机+parent树）

发表于 更新于 分类于 ， ，

F. Forbidden Indices
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a string s consisting of n lowercase Latin letters. Some indices in this string are marked as forbidden.

You want to find a string a such that the value of |a|·f(a) is maximum possible, where f(a) is the number of occurences of a in s such that these occurences end in non-forbidden indices. So, for example, if s is aaaa, a is aa and index 3 is forbidden, then f(a) = 2 because there are three occurences of a in s (starting in indices 1, 2 and 3), but one of them (starting in index 2) ends in a forbidden index.

Calculate the maximum possible value of |a|·f(a) you can get.

Input
The first line contains an integer number n (1 ≤ n ≤ 200000) — the length of s.

The second line contains a string s, consisting of n lowercase Latin letters.

The third line contains a string t, consisting of n characters 0 and 1. If i-th character in t is 1, then i is a forbidden index (otherwise i is not forbidden).

Output
Print the maximum possible value of |a|·f(a).

Examples
input
5
ababa
00100
output
5
input
5
ababa
00000
output
6
input
5
ababa
11111
output
0

题目链接：CF 873F
先构造后缀自动机，然后根据parent树的性质：某一个子树的节点个数就是以这个节点作为结尾的子串的出现次数，建树的时候把可以出现的位置赋值为$1$，否则为$0$，然后对于拷贝的位置全部赋值为$0$（这点很重要），因为它只是作为拷贝，并不属于原字符串；
然后自下向上叠加$sum$最后遍历一遍节点更新答案：$ans = \max{L[i].sum * L[i].len}$，怎么自下向上叠加呢，代码用了按照$len$的计数排序，也可以$dfs$……
代码：

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 200010;
struct Trie
{
    int nxt[26], pre, len;
    LL v;
    void init()
    {
        for(int i = 0; i < 26; ++i)
            nxt[i] = -1;
        pre = -1;
        v = 0LL;
    }
} L[N << 1];
int sz, last;
char s[2][N];
int cnt[N], x[N << 1];

inline void init()
{
    sz = last = 0;
    CLR(cnt, 0);
    L[sz++].init();
}
inline int newnode()
{
    L[sz].init();
    return sz++;
}
void ins(int c, int x)
{
    int u = newnode();
    L[u].len = L[last].len + 1;
    L[u].v = (LL)x;
    int t = last;
    while(t != -1 && L[t].nxt[c] == -1)
    {
        L[t].nxt[c] = u;
        t = L[t].pre;
    }
    if(t == -1)
        L[u].pre = 0;
    else
    {
        int v = L[t].nxt[c];
        if(L[t].len + 1 == L[v].len)
            L[u].pre = v;
        else
        {
            int np = newnode();
            L[np] = L[v];
            L[np].len = L[t].len + 1;
            L[np].v = 0;
            L[np].pre = L[v].pre;
            L[u].pre = L[v].pre = np;
            while(t != -1 && L[t].nxt[c] == v)
            {
                L[t].nxt[c] = np;
                t = L[t].pre;
            }
        }
    }
    last = u;
}
int main(void)
{
    int len, i;
    while(~scanf("%d%s%s", &len, s[0], s[1]))
    {
        init();
        for(i = 0; i < len; ++i)
            ins(s[0][i] - 'a', (s[1][i] - '0') ^ 1);
        LL ans = 0;
        for(i = 0; i < sz; ++i)
            ++cnt[L[i].len];
        for(i = 1; i <= len; ++i)
            cnt[i] += cnt[i - 1];
        for(i = sz - 1; i >= 1; --i)
            x[--cnt[L[i].len]] = i;
        for(i = sz - 1; i >= 1; --i)
        {
            int u = x[i];
            L[L[u].pre].v += L[u].v;
            ans = max(ans, (LL)L[u].len * L[u].v);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}