一道 \(AC\) 自动机 \(+\) 线段树难题。
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 3e5+10;
template<typename T, int NN>
struct Segment_Tree{
T tree[NN<<2], tag[NN<<2];
void pushup(T k){
tree[k] = max(tree[k<<1], tree[k<<1|1]);
}
void pushdown(T k){
if(tag[k] == 0) return;
tree[k<<1] = max(tree[k<<1], tag[k]);
tree[k<<1|1] = max(tree[k<<1|1], tag[k]);
tag[k<<1] = max(tag[k<<1], tag[k]);
tag[k<<1|1] = max(tag[k<<1|1], tag[k]);
tag[k] = 0;
}
void build(T k, T l, T r){
tree[k] = tag[k] = 0;
if(l == r) return;
T mid = l + r >> 1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
}
void modify(T k, T l, T r, T x, T y, T w){
if(l >= x and r <= y){
tree[k] = max(tree[k], w);
tag[k] = max(tag[k], w);
return;
}
T mid = l + r >> 1;
pushdown(k);
if(x <= mid) modify(k<<1, l, mid, x, y, w);
if(y > mid) modify(k<<1|1, mid+1, r, x, y, w);
pushup(k);
}
T ask(T k, T l, T r, T x){
if(l == r){
return tree[k];
}
T mid = l + r >> 1;
pushdown(k);
if(x <= mid) return ask(k<<1, l, mid, x);
else return ask(k<<1|1, mid+1, r, x);
}
};
#include <queue>
#include <vector>
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
#define _rep(i, a, b) for(int i = (a); i < (b); i ++)
template<typename T, int NN>
struct Aho_Corsick_Automaton{
int nxt[NN][28], fail[NN], cnt, vis[NN];
int newnode(){
int x = cnt++;
memset(nxt[x], 0, sizeof nxt[x]);
fail[x] = 0, vis[x] = 0;
return x;
}
int idx(char c){
return c - 'a' + 1;
}
void init(){
cnt = 0;
newnode();
}
void insert(char *s){
int len = strlen(s), u = 0;
_rep(i, 0, len){
int c = idx(s[i]);
if(!nxt[u][c]) nxt[u][c] = newnode();
u = nxt[u][c];
}
}
void failure_function(vector<int> *links){
queue<int> q;
_for(i, 1, 26){
if(nxt[0][i]) q.push(nxt[0][i]);
}
while(!q.empty()){
int u = q.front(); q.pop();
_for(c, 1, 26){
int v = nxt[u][c];
if(!v){
nxt[u][c] = nxt[fail[u]][c];
continue;
}
fail[v] = nxt[fail[u]][c];
q.push(v);
}
links[fail[u]].push_back(u);
}
}
};
#include <string>
Segment_Tree<int, N> segment_tree;
Aho_Corsick_Automaton<int, N> AC_Automaton;
int n, w[N];
char moban[N];
string S[N];
vector<int> link[N];
int L[N], R[N], Tot;
void dfs(int x){
L[x] = ++Tot;
for(auto y:link[x]){
dfs(y);
}
R[x] = Tot;
}
int main(){
int T;
scanf("%d", &T);
_for(kase, 1, T){
memset(L, 0, sizeof L);
memset(R, 0, sizeof R);
scanf("%d", &n);
Tot = 0;
AC_Automaton.init();
_for(i, 1, n){
scanf("%s%d", moban, &w[i]);
AC_Automaton.insert(moban);
S[i] = string(moban);
}
_for(i, 0, AC_Automaton.cnt + 1) link[i].clear();
AC_Automaton.failure_function(link);
dfs(0); int ans = 0;
segment_tree.build(1, 1, Tot);
_for(i, 1, n){
int sum = 0, length = S[i].size(), u = 0;
_rep(j, 0, length){
u = AC_Automaton.nxt[u][AC_Automaton.idx(S[i][j])];
sum = max(sum, segment_tree.ask(1, 1, Tot, L[u]) + w[i]);
}
ans = max(ans, sum);
segment_tree.modify(1, 1, Tot, L[u], R[u], sum);
}
printf("Case #%d: %d\n", kase, ans);
}
return 0;
}