【Trie】 UVA1401 Remember the Word - 教程

代码

#include <string.h>#include <stdlib.h>#include <algorithm>#include <vector>#include <functional>#include <math.h>#include <string>#include <iostream>using namespace std;typedef long long ll;typedef pair<int, int> pii;#define _for(i, a, b) for (int i = (a); i < (b); i++)#define _rep(i, a, b) for (int i = (a); i <= (b); i++)#define fio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)#define reg register#define ri reg intnamespace faio{char buf[1 << 20], *p1, *p2;#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF: *p1++)template <typename T> inline void read(T &t) {ri v = getchar();T f = 1;t = 0;while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}while (isdigit(v)) {t = (t << 3) + (t << 1) + v - '0';v = getchar();}t *= f;}template <typename T,typename... Args> inline void read(T &t, Args&... args) {read(t);read(args...);}}constexpr int N = 300010, mod = 20071027;char str[N], word[128];int dp[N];typedef struct Trie_t{bool is_end;Trie_t* son[26];}*Trie;Trie NewNode() {Trie ret = (Trie) malloc(sizeof(Trie_t));for (int i = 0; i < 26; i++) ret->son[i] = NULL;ret->is_end = false;return ret;}void FreeNode(Trie p) { // 释放 Trie 树if (p == NULL) return ;for (int i = 0; i < 26; i++) FreeNode(p->son[i]);free(p);}void insert(Trie root, const char* _str){Trie u = root; int len = strlen(_str);for (int i = 0; i < len; i++) {int idx = _str[i] - 'a';if (u == NULL) printf("u is NULL");if (u->son[idx] == NULL) u->son[idx] = NewNode();u = u->son[idx];}u->is_end = true;}void solve(Trie root){static int Kase = 0;int n = strlen(str); dp[n] = 1;for (int i = n - 1; i >= 0; i--) {// 在 Trie 树里面找Trie u = root;for (int j = i; j < n; j++) {int idx = str[j] - 'a';if (u->son[idx] == NULL) break;u = u->son[idx];if (u->is_end) dp[i] = (dp[i] + dp[j + 1] + mod) % mod;}}printf("Case %d: %d\n", ++Kase, dp[0]);}int main(){while (scanf("%s", str) == 1) {int p; scanf("%d", &p);Trie root = NewNode();memset(dp, 0, sizeof(dp));while (p--) {scanf("%s", word);insert(root, word);}solve(root);FreeNode(root);}return 0;}