1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <vector>
6 using namespace std;
7 const int M = 20071027;
8 const int maxn = 300000 + 10;
9 const int maxnode = 400000+10;
10 const int _size = 26;
11
12 struct Trie {
13 int ch[maxnode][_size];
14 int val[maxnode];
15 int sz;
16 Trie() {
17 sz = 1;
18 memset(ch[0], 0, sizeof (ch[0]));
19 }
20 int idx(int c) {return c - 'a';}
21
22 void insert(char *s, int v) { //插入字符串s和权值v
23 int u = 0, n = strlen(s);
24 for(int i = 0; i < n; i++) {
25 int c = idx(s[i]);
26 if(!ch[u][c]) {
27 memset(ch[sz], 0, sizeof (ch[sz]));
28 val[sz] = 0;
29 ch[u][c] = sz++;
30 }
31 u = ch[u][c];
32 }
33 val[u] = v;
34 }
35 void find_prefixes(const char *s, int len, vector<int>& ans) { //寻找字符串s的前缀
36 int u = 0;
37 for(int i = 0; i < len; i++) {
38 if(s[i] == '
