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