**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 .

- 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 .
- 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

- 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 ...

- 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 ...

- AC automata & 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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. ...

- 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 ...

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

- 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 ...

- 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. ...