AC Automata related :

$fail$ Trees :

$fail$ The longest tree is $border$ Relationships form father son relationships , We define the string corresponding to a node as the path from the root to the node .

For any non root node $x$, set $y = fa_{x}$, that $y$ The corresponding string is $x$ The longest of the corresponding string $border$, That is to say, if the main string can go to $x$, There must be a substring in the parent string corresponding to $y$, And it is a suffix that matches the current parent string to the current position .

Find the number of times each mode string appears in the parent string :

This is supposed to be AC The most basic problem of automata .

Run the string on the automaton , Obviously, all the visited nodes are substrings of the parent string , But there may be more than one pattern string suffixed by the current matching position , And all of it $border$. A good property is ,$fail$ The ancestor chain of a node in the tree exactly corresponds to all of the nodes $border$. We use it $cnt_{i}$ Express $i$ The number of valid nodes in the ancestor chain of a point , So just match to a node every time $x$ when , It's $cnt_{x}$ Add in the contribution .

If you want to support dynamic addition and subtraction mode string , Because modifying the validity of a node will only affect all nodes in its subtree , Just maintain it $Dfs$ The information in the order is enough .

AC On automata $Dp$ problem

Usually , This kind of $Dp$ The data range of the problem is small , The basic routine of design state usually has two dimensions , One dimension is where the parent string matches , One dimension is the position on the automata , Transfers are basically enumeration characters .

$\star$ A simple example , Is to give a number $n$ and $m$ A string , The length of the question is $n$ How many strings satisfy this $m$ Each string is its substring . Topic link

because $m$ A very small , We just press it up , Indicates which substrings are included in the corresponding string of the node ,$Dp$ There are two ways ,$Dfs$ and $Bfs$ Fine , If $Dfs$ The meaning of state is usually expressed as the number of schemes from the current state to the end state .

However, because this question has to output a plan , use $Bfs$ It's not easy , Or use it $Dfs$ . .

#include <cstdio>
#include <queue>
#include <cstring> using namespace std; typedef long long LL;
const int N = , M = ; int n, m, ST, tot;
char sr[];
int ch[M][], fail[M], fir[M];
queue<int> Q; LL dp[N][M][], ans; void Ins(char *s, int id) {
int pos = ;
for (int i = ; s[i]; ++i) {
int nx = s[i] - 'a';
if (!ch[pos][nx]) {
ch[pos][nx] = ++tot;
memset(ch[tot], , sizeof ch[tot]);
fir[tot] = fail[tot] = ;
}
pos = ch[pos][nx];
}
fir[pos] |= << id;
} void Build() {
Q.push();
for (; !Q.empty(); ) {
int x = Q.front(); Q.pop();
for (int i = ; i < ; ++i) {
int v = ch[x][i];
if (!v) ch[x][i] = ch[fail[x]][i]; else Q.push(v);
if (x && v) fail[v] = ch[fail[x]][i], fir[v] |= fir[fail[v]];
}
}
} LL Dfs(int x, int p, int s) {
if (~dp[x][p][s]) return dp[x][p][s];
if (x == n) {
dp[x][p][s] = (LL) (s == ST);
return dp[x][p][s];
}
dp[x][p][s] = ;
for (int i = ; i < ; ++i) {
int np = ch[p][i];
dp[x][p][s] += Dfs(x + , np, s | fir[np]);
}
return dp[x][p][s];
} void F_(int x, int p, int s) {
if (x == n) {
sr[x] = '\0';
printf("%s\n", sr);
return;
}
for (int i = ; i < ; ++i) {
int np = ch[p][i];
if (dp[x + ][np][s | fir[np]]) {
sr[x] = 'a' + i;
F_(x + , np, s | fir[np]);
sr[x] = '\0';
}
}
} void Clear() {
memset(dp, -, sizeof dp);
memset(ch[], , sizeof ch[]);
tot = ans = ;
} int main() {
for (int tc = ; scanf("%d%d", &n, &m) == && n + m > ; ) {
Clear();
ST = ( << m) - ;
for (int i = ; i < m; ++i) {
scanf("%s", sr);
Ins(sr, i);
}
Build();
ans = Dfs(, , );
printf("Case %d: %lld suspects\n", ++tc, ans);
if (ans <= ) {
memset(sr, , sizeof sr);
F_(, , );
}
} return ;
}

Suffix automata related :

$parent$ Trees :

$parent$ The relationship between father and son is formed in the tree , For any non root node, there are $dep_{i} - dep_{fa_{i}}$ For the node $i$ The number of substrings contained .

Find the number of non repeating substrings of a string :

This is a classic problem on suffix automata , Most of the time, it will be used as a sub problem to solve a problem . In fact, it's easy to think of , Each substring is represented by a node on the automata , All the same substrings will only be represented once , Repeated will count in $right$ It's in the assembly . The number of unrepeated substrings in each node is $max_{i} - min_{i} + 1$ A continuous period of , Add the number of non repeating substrings contained in all nodes .

$ans = \sum\limits_{i = 1}^{tot} dep_{i} - dep_{fa_{i}}$.

Sort all substrings in dictionary order :

Because the lexicographic order compares prefixes , Usually we build the inverse string into a suffix automaton , The substrings represented on that node all have the same suffix , Corresponding to the prefix of the original string , Then we just need to sort the inverse strings in the sense of suffix . Obviously , All substrings represented in a node must be continuous in the suffix dictionary order . therefore , We have to $parent$ Every node in the tree $x$, hypothesis $y = fa_{x}$,$x$ The shortest substring ratio in $y$ The character with the longest substring in $a$ It will be there. $y$ The first space of the longest string in , Then we'll make it $son_{y,a} = x$. obviously ,$son$ It means a tree , Of this tree $Dfs$ Order is the suffix dictionary order that we require for each node , Because we're working on it $Dfs$ The next string with smaller character will be selected first .

The following is the implementation of the specific tree :

void Dfs(int t) {
id[++tp] = t;
for (int i = ; i < ; ++i) {
if (son[t][i]) Dfs(son[t][i]);
}
} void Build() {
for (int i = ; i <= tot; ++i) ++bit[dep[i]];
for (int i = ; i <= tot; ++i) bit[i] += bit[i - ];
for (int i = tot; i >= ; --i) id[bit[dep[i]]--] = i;
for (int i = tot; i >= ; --i) {
int x = id[i];
son[fa[x]][s[ed[x] - dep[fa[x]]] - 'a'] = x;
}
Dfs();
}

( notes : among $ed_{i}$ Representation node $i$ Indicates the position of the character at the end of the substring )

Find out the order of the dictionary $k$ Little boy string :

There are two kinds of punishment , One is to calculate repeated substrings , One is not a repeating substring , There is no difference in essence , If we calculate the repeated substring, we just multiply each node by $right$ Set size is OK .

With the last model , All we have to do is $Dfs$ After the sequence on the two can be , Maintain a prefix of $sum_{i}$ Before presentation $i$ How many substrings are represented by nodes , Two points can find the second $k$ The node where the substring is located , You'll know it's the string . The above is not repeated substring , If you count the repeating substrings , Because of the $right$ The set size is the same , So when we calculate the number of substrings, we multiply by $right$ Set size is enough , Another question , If it's a repeating substring , When we find out the specific position of the substring, we usually need another dichotomy to determine its length .

Determine the lexicographic order of a substring in all substrings :

With $[l,r]$ Give a substring in the form of , set up $pos_{i}$ For the first time $i$ New node created when a string is inserted , Because nodes that are suffixes of each other are in $parent$ The tree forms a chain to the root , Obviously substring $[l,r]$ Will appear in $pos_{r}$ On the chain of our ancestors , We can use the tree multiplication to find the inclusion $[l,r]$ The node . We can do that , Because the length of the substring decreases monotonously with the depth of the node , And the length range of substrings has no intersection .

$\star$ The following problem is an application of the dictionary order of substring , There is no difficulty in mastering this routine , This is just an example . Topic link

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; typedef long long LL;
const int N = ; int n, Qi, tp, gans, ans;
char s[N];
LL sum[N]; int tot, lst, ch[N][], dep[N], fa[N], rig[N];
int id[N], bit[N], ed[N], son[N][];
inline int New_(int _d, int _f, int _r, int _e) {
dep[++tot] = _d; fa[tot] = _f; rig[tot] = _r; ed[tot] = _e;
return tot;
}
inline void Ins(int a, int i) {
int np = New_(dep[lst] + , , , i), p = lst;
lst = np;
for (; p && !ch[p][a]; p = fa[p]) ch[p][a] = np;
if (!p) return void(fa[np] = );
int q = ch[p][a];
if (dep[p] + == dep[q]) return void(fa[np] = q);
int y = New_(dep[p] + , fa[q], , ed[q]);
memcpy(ch[y], ch[q], sizeof ch[y]);
fa[q] = fa[np] = y;
for (; p && ch[p][a] == q; p = fa[p]) ch[p][a] = y;
}
void Build() {
for (int i = ; i <= tot; ++i) ++bit[dep[i]];
for (int i = ; i <= tot; ++i) bit[i] += bit[i - ];
for (int i = tot; i >= ; --i) id[bit[dep[i]]--] = i;
for (int i = tot; i >= ; --i) {
int x = id[i];
rig[fa[x]] += rig[x];
ed[fa[x]] = ed[x]; // a question for why it is used
son[fa[x]][s[ed[x] - dep[fa[x]]] - 'a'] = x;
}
} void Dfs(int t) {
id[++tp] = t;
for (int i = ; i < ; ++i) {
if (son[t][i]) Dfs(son[t][i]);
}
} LL Get(int l, int r) {
if (l > r) return ;
return (LL) (l + r) * (r - l + ) / ;
} int Solve(LL k) {
int nl = , nr = tot, po = -;
for (int md; nl <= nr; ) {
md = (nl + nr) >> ;
if (sum[md] >= k) {
po = md; nr = md - ;
} else {
nl = md + ;
}
}
if (po == -) throw;
k -= sum[po - ];
int L = dep[fa[id[po]]] + , R = dep[id[po]], re = -;
nl = L; nr = R;
for (int md; nl <= nr; ) {
md = (nl + nr) >> ;
if (k <= rig[id[po]] * Get(L, md)) {
re = md; nr = md - ;
} else {
nl = md + ;
}
}
if (re == -) throw;
k -= rig[id[po]] * Get(L, re - );
k = (k - ) % re + ;
return s[ed[id[po]] - k + ];
} int main() {
scanf("%s", s + );
n = strlen(s + );
std::reverse(s + , s + + n);
tot = lst = ;
for (int i = ; s[i]; ++i) Ins(s[i] - 'a', i);
Build();
Dfs();
for (int i = ; i <= tot; ++i) {
sum[i] = sum[i - ] + rig[id[i]] * Get(dep[fa[id[i]]] + , dep[id[i]]);
} scanf("%d", &Qi);
for (LL p, m, k; Qi; --Qi) {
scanf("%lld%lld", &p, &m);
k = gans * p % m + ;
ans = Solve(k);
printf("%c\n", ans);
gans += ans;
} return ;
}

  Maintain each node's $right$ aggregate :

A lot of times we have to use $right$ Information about collections , It's all right $right$ The size of the set adds up to $O(n^{2})$ Of , Fortunately $right$ Set has an important superior property , about $parent$ Every node in the tree , its $right$ It must be his father's $right$ The proper subset of a set , And with its brothers $right$ Sets don't intersect . So we can use segment tree merging to maintain , Every time I go from leaf to root, I merge information into my father , It's important to note that we don't want to change the original information when merging , So when merging, you need to create a new node , So the complexity of time and space is $O(nlogn)$ Of .

$\star$ The following question is about the merging and maintenance of line segment trees $right$ Applications of collections , The specific idea is the length of the binary answer string , After finding the node of the substring, ask $right$ Is there... In the collection . Topic link

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int N = , LOG = ; int n, m;
int Rt[N], gr[LOG][N];
char s[N]; namespace SE {
const int M = N * ;
int tot, lc[M], rc[M], sum[M];
void Modify(int &t, int l, int r, int x) {
if (!t) t = ++tot;
++sum[t];
if (l == r) return;
int md = (l + r) >> ;
if (x <= md) Modify(lc[t], l, md, x);
else Modify(rc[t], md + , r, x);
}
int Merge(int x, int y) {
if (!x || !y) return x + y;
int z = ++tot;
lc[z] = Merge(lc[x], lc[y]);
rc[z] = Merge(rc[x], rc[y]);
sum[z] = sum[lc[z]] + sum[rc[z]];
return z;
}
int Query(int t, int l, int r, int L, int R) {
int md = (l + r) >> , re = ;
if (L <= l && r <= R) return sum[t];
if (L <= md) re += Query(lc[t], l, md, L, R);
if (R > md) re += Query(rc[t], md + , r, L, R);
return re;
}
} int tot = , lst = , ch[N][], dep[N], fa[N];
int bit[N], id[N], pos[N];
inline int New_(int _dep, int _fa) {
dep[++tot] = _dep; fa[tot] = _fa;
return tot;
}
void Ins(int a, int i) {
int np = New_(dep[lst] + , ), p = lst;
lst = np; pos[i] = tot;
SE::Modify(Rt[tot], , n, i);
for (; p && !ch[p][a]; p = fa[p]) ch[p][a] = np;
if (!p) return void(fa[np] = );
int q = ch[p][a];
if (dep[q] == dep[p] + ) return void(fa[np] = q);
int y = New_(dep[p] + , fa[q]);
memcpy(ch[y], ch[q], sizeof ch[y]);
fa[q] = fa[np] = y;
for (; p && ch[p][a] == q; p = fa[p]) ch[p][a] = y;
}
void Build() {
for (int i = ; i <= tot; ++i) ++bit[dep[i]];
for (int i = ; i <= tot; ++i) bit[i] += bit[i - ];
for (int i = ; i <= tot; ++i) id[bit[dep[i]]--] = i;
for (int i = ; i <= tot; ++i) {
int x = id[i]; gr[][x] = fa[x];
for (int j = ; j < LOG; ++j) gr[j][x] = gr[j - ][gr[j - ][x]];
}
for (int i = tot; i >= ; --i) {
int x = id[i], y = fa[x];
Rt[y] = SE::Merge(Rt[x], Rt[y]);
}
} int Check(int x, int md, int l, int r) {
if (l > r) return ;
for (int i = LOG - ; ~i; --i) {
if (gr[i][x] && dep[gr[i][x]] >= md) x = gr[i][x];
}
return SE::Query(Rt[x], , n, l, r) > ;
} int main() {
scanf("%d%d", &n, &m);
scanf("%s", s + );
reverse(s + , s + + n);
for (int i = ; i <= n; ++i) Ins(s[i] - 'a', i);
Build(); for (int a, b, c, d; m; --m) {
scanf("%d%d%d%d", &a, &b, &c, &d);
a = n - a + ; b = n - b + ; swap(a, b);
c = n - c + ; d = n - d + ; swap(c, d);
int nl = , nr = d - c + , re = ;
for (int md; nl <= nr; ) {
md = (nl + nr) >> ;
if (Check(pos[d], md, a + md - , b)) {
re = md; nl = md + ;
} else {
nr = md - ;
}
}
printf("%d\n", re);
} return ;
}

$\star$ With the above as the basis , We can solve the following problem , There are two questions .

  1. Given $k1,k2$, Find the order of the dictionary in the unrepeated substring $k1$ Small substrings , And in all the same substrings, find the left to right $k2$ individual , With $[l,r]$ Return the answer in the form of .
  2. With $[l,r]$ In the form of stator string , Find its lexicographic rank in all non repeating substrings $k1$, And ranking from left to right in all the same substrings $k2$, return $k1,k2$.

For the first question :

We according to the $son$ Treelike $Dfs$ You can know the order of the dictionary $k1$ The node where the small substring is located $x$, And then we want to know $x$ Of $right$ The second part of the set $k2$ Where are the elements , You can divide it into two parts on the line tree .

For the second question :

We are $parent$ Multiply the tree to find the substring $[l,r]$ The node $x$, And then we want to know $r$ This position is $x$ Of $right$ What's the number in the collection , You can divide it into two parts on the line tree .

What I want to say is , About dictionary order 、 Substring and so on are all problems of comparative routines , Just master the skills .

This is the implementation of the problem : Original address

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; typedef long long LL;
const int N = , LOG = ; int n, m, tp;
int Rt[N], gr[LOG][N];
char s[N], ssr[];
LL sum[N]; inline void Read(LL &x) {
x = ; static char c;
for (c = getchar(); c < '' || c > ''; c = getchar());
for (; c >= '' && c <= ''; x = (x << ) + (x << ) + c - '', c = getchar());
} namespace SE {
const int M = N * ;
int tot, lc[M], rc[M], sum[M];
void Modify(int &t, int l, int r, int x) {
if (!t) t = ++tot;
++sum[t];
if (l == r) return;
int md = (l + r) >> ;
if (x <= md) Modify(lc[t], l, md, x);
else Modify(rc[t], md + , r, x);
}
int Merge(int x, int y) {
if (!x || !y) return x + y;
int z = ++tot;
lc[z] = Merge(lc[x], lc[y]);
rc[z] = Merge(rc[x], rc[y]);
sum[z] = sum[lc[z]] + sum[rc[z]];
return z;
}
int Query_1(int t, int l, int r, int k) {
if (l == r) return l;
int md = (l + r) >> ;
if (sum[lc[t]] >= k) return Query_1(lc[t], l, md, k);
return Query_1(rc[t], md + , r, k - sum[lc[t]]);
}
int Query_2(int t, int l, int r, int k) {
if (l == r) return sum[t];
int md = (l + r) >> ;
if (k <= md) return Query_2(lc[t], l, md, k);
return sum[lc[t]] + Query_2(rc[t], md + , r, k);
}
} int tot = , lst = , ch[N][], dep[N], rig[N], fa[N], ed[N];
int bit[N], id[N], rk[N], pos[N], son[N][];
inline int New_(int _dep, int _fa, int _ri, int _e) {
dep[++tot] = _dep; fa[tot] = _fa; rig[tot] = _ri; ed[tot] = _e;
return tot;
}
void Ins(int a, int i) {
int np = New_(dep[lst] + , , , i), p = lst;
lst = np; pos[i] = tot;
SE::Modify(Rt[tot], , n, i);
for (; p && !ch[p][a]; p = fa[p]) ch[p][a] = np;
if (!p) return void(fa[np] = );
int q = ch[p][a];
if (dep[q] == dep[p] + ) return void(fa[np] = q);
int y = New_(dep[p] + , fa[q], , ed[q]);
memcpy(ch[y], ch[q], sizeof ch[y]);
fa[q] = fa[np] = y;
for (; p && ch[p][a] == q; p = fa[p]) ch[p][a] = y;
}
void Dfs(int x) {
id[++tp] = x;
for (int i = ; i < ; ++i) {
if (son[x][i]) Dfs(son[x][i]);
}
}
void Build() {
for (int i = ; i <= tot; ++i) ++bit[dep[i]];
for (int i = ; i <= tot; ++i) bit[i] += bit[i - ];
for (int i = ; i <= tot; ++i) id[bit[dep[i]]--] = i;
for (int i = ; i <= tot; ++i) {
int x = id[i]; gr[][x] = fa[x];
for (int j = ; j < LOG; ++j) gr[j][x] = gr[j - ][gr[j - ][x]];
}
for (int i = tot; i >= ; --i) {
int x = id[i], y = fa[x];
rig[y] += rig[x];
Rt[y] = SE::Merge(Rt[x], Rt[y]);
son[y][s[ed[x] - dep[y]] - 'a'] = x;
}
Dfs();
if (tp != tot) { cerr << "not tp equal!" << endl; throw; }
for (int i = ; i <= tot; ++i) {
rk[id[i]] = i;
sum[i] = sum[i - ] + dep[id[i]] - dep[fa[id[i]]];
}
} pair<LL, LL> Solve_1(LL k1, int k2) {
int nl = , nr = tot, x = -;
for (int md; nl <= nr; ) {
md = (nl + nr) >> ;
if (k1 <= sum[md]) {
x = md; nr = md - ;
} else {
nl = md + ;
}
}
if (x == -) { cerr << "not found po!" << endl; throw; }
k1 -= sum[x - ];
x = id[x];
if (k2 > rig[x]) { cerr << "k2" << endl; throw; }
k2 = rig[x] - k2 + ;
int ps = SE::Query_1(Rt[x], , n, k2);
int len = k1 + dep[fa[x]];
return make_pair(ps - len + , ps);
}
pair<LL, LL> Solve_2(int l, int r) {
int x = pos[r], le = r - l + ;
for (int i = LOG - ; ~i; --i) {
if (gr[i][x] && dep[gr[i][x]] >= le) x = gr[i][x];
}
int re = SE::Query_2(Rt[x], , n, r);
LL rnk = sum[rk[x] - ] + le - dep[fa[x]];
return make_pair(rnk, rig[x] - re + );
} int main() {
scanf("%s", s + );
n = strlen(s + );
reverse(s + , s + + n);
for (int i = ; i <= n; ++i) Ins(s[i] - 'a', i);
Build(); scanf("%d", &m);
pair<LL, LL> re;
for (LL l, r; m; --m) {
scanf("%s", ssr);
Read(l); Read(r);
if (ssr[] == 'S') {
re = Solve_1(l, r);
re.first = n - re.first + ;
re.second = n - re.second + ;
swap(re.first, re.second);
} else {
l = n - l + ; r = n - r + ; swap(l, r);
re = Solve_2(l, r);
}
printf("%lld %lld\n", re.first, re.second);
} return ;
}

  For two strings of $LCS$($LCP$):

The longest common suffix of the substring is $parent$ The tree is a classic problem , We already know how to find the node of a substring , So the answer node is the node where the two substrings are located $parent$ On the tree $LCA$.

about $LCP$, Just do it for anti string .

Monotonicity of suffix automata on interval :

Usually , The interval problem of suffixes always has monotonicity , Is the existence of substrings . Our interval is substring , obviously , If an interval is a substring of a string , Then its subinterval must be the substring of the string .

Let's look at a simple question , Give a string $S,T$, inquiry $S$ How many substrings are $T$ The string of .

According to the above monotonicity , For each position as the right end of the substring $i$, There is a very left position $l_{i}$ Satisfy all than $l_{i}$ Small positions are illegal , All greater than or equal to $l_{i}$ All the positions are legal , So use $two \; pointers$ Can solve problems . We often use a node on an automata $p$ Represents the current range we maintain ( Substring ), Every time $nr$ Ready to move one space to the right , Equivalent to the $p$ Try to transfer , If there is a transition edge , that $[nl,nr+1]$ That is to say, a legal substring ,$nl$ Immobility ; Otherwise, we need to let $nl$ Move one space to the right , This is equivalent to becoming more than $[nl,nr+1]$ A suffix just one short . There's something to pay attention to here , When it's short for a moment, it's possible that the length of the string will be reduced to the length of its father , That is the string length at this time $len = dep_{fa_{p}}$, At this time, let $p$ Dance once, father .

$\star$ Here we give a problem about monotonicity . Topic link

Can be observed , When we do a copy operation , set up $j$ For the starting point of replication , be $[j + 1, i]$ Must be $[1,j]$ The string of , And this one has the monotonicity we discussed above .

Can be listed $Dp$ The equation of :$dp_{i} = max_{j = k}^{i - 1} \; \{ \; dp_{j} + (i - j) * A + 2 * B \; \}$, And the $dp_{i - 1} + cost_{s_{i}}$ Minimum value , among $k$ It's the smallest position that can be used as a starting point .

Ask for every $i$ Of $k$, You can use the above methods to maintain , It's just that the current automata are $[1,k]$ nothing more , To support dynamic character insertion , May change $p$ The node location of , So in maintenance $p$ Remember to update .

Then we just need to maintain the maximum value of the interval , This is because $k$ It's monotonous , Just use monotonic queue maintenance .

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; typedef long long LL;
const int N = ; int tc, n, kp, le;
char s[N];
int q[N], cost[];
LL dp[N], A, B; int tot, lst, ch[N][], dep[N], fa[N];
inline int New_(int _dep, int _fa) {
dep[++tot] = _dep; fa[tot] = _fa;
memset(ch[tot], , sizeof ch[tot]);
return tot;
}
inline void Ins(int a) {
int np = New_(dep[lst] + , ), p = lst;
lst = np;
for (; p && !ch[p][a]; p = fa[p]) ch[p][a] = np;
if (!p) return void(fa[np] = );
int q = ch[p][a];
if (dep[p] + == dep[q]) return void(fa[np] = q);
int y = New_(dep[p] + , fa[q]);
memcpy(ch[y], ch[q], sizeof ch[y]);
fa[q] = fa[np] = y;
if (kp == q && le <= dep[y]) kp = y;
for (; p && ch[p][a] == q; p = fa[p]) ch[p][a] = y;
} void Clear() {
memset(ch[], , sizeof ch[]);
tot = lst = ;
} int main() {
scanf("%d", &tc);
for (int tm = ; tm <= tc; ++tm) {
Clear();
scanf("%s", s + );
n = strlen(s + );
for (int i = ; i < ; ++i) {
scanf("%d", &cost[i]);
}
scanf("%lld%lld", &A, &B);
int nl = , nr = ; kp = ;
for (int i = , j = ; i <= n; ++i) {
int nc = s[i] - 'a';
dp[i] = dp[i - ] + cost[nc];
while (j <= i && !ch[kp][nc]) {
if (i - j - == dep[fa[kp]]) kp = fa[kp];
le = i - j - ;
Ins(s[j] - 'a'); ++j;
}
if (j <= i) kp = ch[kp][nc];
while (nl <= nr && q[nl] < j - ) ++nl;
if (nl <= nr) dp[i] = min(dp[i], dp[q[nl]] + (i - q[nl]) * A + * B);
while (nl <= nr && dp[q[nr]] - q[nr] * A >= dp[i] - i * A) --nr;
q[++nr] = i;
}
printf("Case #%d: %lld\n", tm, dp[n]);
} return ;
}

【 project 】 String topic summary (AC automata + Postfix automaton ) More articles about

  1. bzoj 3796: Mushroom Chasing girls AC automata + Postfix automaton +dp

    The main idea of the topic : Given three strings s1,s2,s3, Find a string w Satisfy : w yes s1 The string of w yes s2 The string of s3 No w The string of w It should be as long as possible Answer key : First we can use AC Automata find out s3 stay s1,s2 Where in ...

  2. BZOJ2754: [SCOI2012] Roll call on meow (AC automata / Postfix automaton )

    Description a180285 Fortunately, I was selected as an international student from earth to meow . He found it very interesting that meow people call names before class .   Let's say there's N A meow man , Each meow's name consists of a surname and a first name . Teachers on meow will choose M A string ...

  3. AC automata &amp; Postfix automaton

    Understanding is not deep enough So we can only use this to deepen our understanding . I'm just stupid. I can't help it The whole process of the problem that the senior students talked about was hoodwinked . Maybe I'm a dish , Oh, no, I'm a dish . AC The name of the automaton AC From a bull Automata is more particular It's not an ordinary thing ...

  4. BZOJ 3926: [Zjoi2015] The land of fantasy favored by the gods Generalized suffix automata Postfix automaton character string

    https://www.lydsy.com/JudgeOnline/problem.php?id=3926 Generalized suffix automata is a data structure that can process many strings ( Unlike suffix automata, it only deals with one or two kinds of time ...

  5. BZOJ 3998: [TJOI2015] String theory Postfix automaton Suffix automaton k Little boy string

    http://www.lydsy.com/JudgeOnline/problem.php?id=3998 A template for suffix automata application ? Need to be right len Make a sort and then count the number of each occurrence , The maintenance is based on the string ...

  6. BZOJ4032[HEOI2015] The shortest uncommon substring —— Sequential automata + Postfix automaton +DP+ greedy

    Title Description The longest common substring in the . After getting impatient with the subsequence problem , You decide to do the opposite . A string of “ Substring ” It refers to a continuous section of it , for example bcd yes abcdef The string of , but bde No . A string of “ Subsequence ” It means that it can ...

  7. character string [ not AC]( Postfix automaton ):HEOI 2016 str

    Super disgusting , Use... Successively set maintain right, Use the chairman tree to maintain , All timeout , The local test is AC Of . don 't worry ,BZOJ Up or 1S Limit , It seems that only those whose constants are optimized to a certain level can AC Well . All in all, I am a spiritual victory QAQ #include ...

  8. HDU - 6208 The Dominator of Strings HDU - 6208 AC automata || Postfix automaton

    https://vjudge.net/problem/HDU-6208 First of all, the longest string must be the answer then , Equivalent to using n - 1 Two pattern strings to match the main string , See how many match . Ordinary kmp Words , Every time ...

  9. character string (tjoi2016,heoi2016,bzoj4556)(sam( Postfix automaton )+ Line tree merge + Multiply + Two points answer )

    On Jiayuan's birthday , Her little friend bought a birthday present from the East . Birthday presents are in a magic box . It's written on the outside of the box One is long for \(n\) String \(s\), and \(m\) A question . Sister Jiayuan must answer this correctly \(m\) A question , ...

Random recommendation

  1. The thinking logic of computer programs (46) - analyse PriorityQueue

    The last section introduces the basic concept and algorithm of heap , In this section we'll talk about heaping in Java Concrete implementation classes in - PriorityQueue. Let's start with the basic concepts , Then introduce its usage , Then analyze the implementation code , Finally, it summarizes and analyzes its characteristics . Basic concepts Gu Mingsi ...

  2. js An array of operations for splice

    original text : Click to open the link 1. effect : Delete some elements from the specified location and add new ones                1.1. The return value of this method is an array of deleted elements                1.2.splice It's direct ...

  3. Xcode After upgrading , The plug-in can't be used ( PluginLoading: Required plug-in compatibility UUID.... )

    find ~/Library/Application\ Support/Developer/Shared/Xcode/Plug-ins -name Info.plist -maxdepth 3 | x ...

  4. ZEDBOARD Boot configuration ( Load the image ) classification : OpenCV ubuntu shell ZedBoard Eye_Detection 2014-11-08 18:53 167 Human reading Comment on (0) Collection

    Reference resources : Lu Shu 14.2.8 1) Backup ramdisk8M.image.gz 2) load rootfs Image file : 3) Create your own folder in the mirror directory ( Mount Directory ): I need two mount directories : root/qt/ins ...

  5. gulp+webpack+vue

    gulp+webpack+vue Chapter contents 1. The goal is 2. Realization 2.1 Merge library files 2.2 Organization business code 2.3 Package development code 2.4 Use webpack-dev-server And hot swap plug-ins HotModuleR ...

  6. cocos2d-X-3.X Scenes and layers

    1 The correlation function between scene and layer 1. void runWithScene(Scene * scene). This function can run scenarios . This function can only be called when starting the first scene . If there is already a scene running , The function cannot be called . 2.  ...

  7. C++ Different variables in 、 Function in memory 《 turn 》

    One . One C++ The memory occupied by the compiled program is divided into the following parts 1. The stack area : Automatically assigned by the compiler Stores the parameter values of the function , The value of a local variable, etc , The operation is similar to the stack in the data structure . 2. Heap area : Release is usually assigned by the programmer , If programmers don't release , Program conclusion ...

  8. W3C------JS

    *-------------------------------------------- Split line --------------------------------------------* W3C:ht ...

  9. Chapter 10 、4-CSS Classes--- Use multiple CSS Classes Positioning elements

    The following demo operation takes the input box in the website as an example :https://learn.letskodeit.com/p/practice One . Use input[class=inputs] Verify that the element is unique Be careful : Use “clas ...

  10. Memory barriers and volatile Implementation of memory semantics

    Take advantage of the weekend , Take out the old books , Double that , Take a note by the way : Memory barrier : To control and regulate cpu The sequence of memory operations cpu Instructions . Memory barrier list : 1.loadload: Make sure “ The former is data loading ” Precede “ The latter loads instructions ”: 2. ...