1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 |
- // How many Pi are in T ?
- // COMPLEXITY: linear
- // USAGE: call init, insert to create dictionnary (strings are copied), and query
- const int MAXN = 500010;
- const int Alphabet = 26;
- struct Trie {
- int next[MAXN][Alphabet],fail[MAXN],end[MAXN];
- int root, L;
- int newnode() {
- for (int i=0; i<Alphabet; i++) next[L][i] = -1;
- end[L++] = 0;
- return L-1;
- }
- void init() {
- L=0;
- root = newnode();
- }
- void insert(const char buf[]) {
- int len = strlen(buf);
- int now = root;
- for (int i = 0; i < len; i++) {
- if (next[now][buf[i] - 'a'] == -1)
- next[now][buf[i] - 'a'] = newnode();
- now = next[now][buf[i] - 'a'];
- }
- end[now]++;
- }
- void build() {
- queue<int> Q;
- fail[root] = root;
- for (int i = 0; i < Alphabet; i++)
- if (next[root][i] == -1)
- next[root][i] = root;
- else {
- fail[next[root][i]] = root;
- Q.push(next[root][i]);
- }
- while(!Q.empty()) {
- int now = Q.front();
- Q.pop();
- for (int i = 0; i < Alphabet; i++)
- if (next[now][i] == -1)
- next[now][i] = next[fail[now]][i];
- else {
- fail[next[now][i]] = next[fail[now]][i];
- Q.push(next[now][i]);
- }
- }
- }
- int query(const char buf[]) {
- int len = strlen(buf);
- int now = root;
- int res = 0;
- for (int i = 0; i < len; i++) {
- now = next[now][buf[i] - 'a'];
- int temp = now;
- while (temp != root) {
- res += end[temp];
- end[temp] = 0;
- temp = fail[temp];
- }
- }
- return res;
- }
- };
|