动态链表：
#include#include #include #include using namespace std; struct Node{ Node * child[10]; bool bad; Node() //构造函数中初始化。在静态分配时就能初始化。 { memset(child, 0, sizeof(child)); bad = false; }};int nodeCount; //用来指向数组中未分配的单元。bool insertNode(Node *tree, char *s){ int i; Node * p = tree; for(i = 0; s[i+1]; i++) { if(p->child[s[i]-'0'] == 0) { p->child[s[i]-'0'] = tree + nodeCount; //将各个节点按次序分配到数组的相应位置。 nodeCount++; } p = p->child[s[i]-'0']; if(p->bad) //如果遇到危险节点（某个字符串的最后一个节点），则说明该串含有前面的串。 { return false; } } bool ok; if(p->child[s[i]-'0'] == 0) { p->child[s[i]-'0'] = tree + nodeCount; nodeCount++; ok = true; } else //如果最后一个节点已经被分配过，说明该串是前面串的前缀。 ok = false; p = p->child[s[i]-'0']; p->bad = true; //字符串最后一个节点是危险节点。 return ok;}void del(Node *p){ for(int i=0;i<10;i++) { if(p->child[i]) del(p->child[i]); } delete(p);}Node Tree[100000]; //为了避免初始化，直接重新开，分配大小要合适，否则RA。int main(){ int n, i, t; bool ok; scanf("%d", &t); while(t--) { scanf("%d", &n); char s[12]; memset(Tree,0,sizeof(Tree)); nodeCount = 1; ok = true; for(i = 0; i < n; i++) { scanf(" %s", s); if(!insertNode(Tree, s)) { ok = false; } } if(ok) printf("YES\n"); else printf("NO\n"); } return 0;}
静态数组模拟模板：
#include#include #include using namespace std;const int M = 33333;const int N = 27;char st[M][N];int tot,size,sz;int trie[M*10][N],num[10*M];void insert(char *st){ int len=strlen(st+1); int now=0; for(int i=1;i<=len;i++){ int k=st[i]-'a'; if(trie[now][k]==0) trie[now][k]=++sz; now=trie[now][k]; num[now]++; }}void ask(char *st){ int now=0,k,len=strlen(st+1); for(int i=1;i<=len;i++){ if(num[now]==1) break; k=st[i]-'a'; printf("%c",st[i]); now=trie[now][k]; }}int main(){ while(~scanf("%s",st[++tot]+1)) insert(st[tot]); for(int i=1;i<=tot;i++){ printf("%s ",st[i]+1); ask(st[i]); printf("\n"); } return 0;}