有一个只包含小写字母,长度为nn 的字符串SS。有一些字母是好的,剩下的是坏的。

定义一个子串Sl..rS_{l..r}是好的,当且仅当这个子串包含不超过kk个坏的字母。

求有多少个不同的满足以下要求的字符串TT

  • TT作为SS的子串出现过。
  • 存在一个TT出现的位置[l,r][l, r],满足Sl..rS_{l..r}是好的

n,k105n, k\le 10^5

LOJ6401

Solution

傻逼题,用来在考前稍微复习一下SAM

考虑和统计本质不同子串个数类似的做法

posipos_i表示以ii为右端点,满足子串包含不超过kk个坏字母的左端点的最小值,leni=iposi+1len_i = i - pos_i + 1

显然对于SAM的每个节点,它right集合中所有右端点的lenlen的最大值,就是这个节点所代表的子串中最长满足条件的长度,与[minlen,maxlen][minlen, maxlen]取交集即为这个节点的答案

感觉没写太清楚,反正这题比较水随便想想就会了。。。

Code

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
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;

int N, K, A[Maxn];
char S[Maxn], SS[Maxn];

int Root[Maxn << 1], Sum[Maxn], Len[Maxn];

namespace SAM
{
int node_cnt = 1, last = 1;

struct info
{
int ch[27], fa, maxlen, max;
} node[Maxn << 1];
vector <int> G[Maxn << 1];

inline int new_node (int pos)
{
node[++node_cnt].maxlen = node[last].maxlen + 1;
node[node_cnt].max = Len[pos];
return node_cnt;
}

inline int extend (int c, int pos)
{
int now = new_node (pos), pre = last; last = now;

for (; pre && !node[pre].ch[c]; pre = node[pre].fa) node[pre].ch[c] = now;

if (!pre) node[now].fa = 1;
else
{
int x = node[pre].ch[c];
if (node[x].maxlen == node[pre].maxlen + 1) node[now].fa = x;
else
{
int y = ++node_cnt; node[y] = node[x];
node[y].maxlen = node[pre].maxlen + 1, node[x].fa = node[now].fa = y;
for (; node[pre].ch[c] == x; pre = node[pre].fa) node[pre].ch[c] = y;
}
}

return now;
}

inline void dfs (int x)
{
for (int i = 0; i < G[x].size(); ++i)
{
int y = G[x][i];
dfs (y);
Chkmax (node[x].max, node[y].max);
}
}

inline void build (char *s, int n)
{
for (int i = 1; i <= n; ++i) extend (s[i] - 'a', i);
for (int i = 1; i <= node_cnt; ++i) G[node[i].fa].pb (i);
dfs (1);
}

inline int calc (int l1, int r1, int l2, int r2)
{
Chkmax (l1, l2), Chkmin (r1, r2);
return r1 - l1 + 1;
}

inline void solve ()
{
LL ans = 0;
for (int i = 1; i <= node_cnt; ++i)
{
int sum = max(0, calc (node[node[i].fa].maxlen + 1, node[i].maxlen, 1, node[i].max));
ans += sum;
}
cout << ans << endl;
}
}

inline void Solve ()
{
int pos = 1;
for (int i = 1; i <= N; ++i)
{
while (Sum[i] - Sum[pos - 1] > K) ++pos;
Len[i] = i - pos + 1;
}

SAM :: build (S, N);

SAM :: solve ();
}

inline void Input ()
{
scanf("%s", S + 1), N = strlen (S + 1);
scanf("%s", SS + 1);
for (int i = 1; i <= N; ++i) A[i] = !(SS[i] - '0'), Sum[i] = Sum[i - 1] + A[i];
K = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}