这里涉及左孩子右兄弟的遍历方法,dfs在dfsnextsibling是floor 并不加一
#include<cstdio> #include <vector> #include<cstring> #include<iostream> #include <set> #include <algorithm> using namespace std; #define INF 1000000; typedef struct node{ char c; int tot; node *firstchild,*nextsibling; node():c('\0'),tot(0),firstchild(NULL),nextsibling(NULL){} }node,*pointer; struct Trie{ pointer root; Trie(){root=new node();} void insert(char* s,int n ){ pointer u=root; for(int i=0;i<n;i++){ pointer p=u->firstchild; if(p!=NULL) while(p->nextsibling!=NULL&&p->c!=s[i]) p=p->nextsibling; if(p==NULL||p->nextsibling==NULL&&p->c!=s[i]){ pointer& v=(p==NULL ? u->firstchild:p->nextsibling); v=new node(); v->c=s[i]; v->tot++; u=v; } else { u=p; u->tot++;} } } bool find(char* s,int n){ pointer u=root; for(int i=0;i<n;i++){ pointer p=u->firstchild; if(p==NULL) return false; while(p->nextsibling!=NULL&&p->c!=s[i]) p=p->nextsibling; if(p->nextsibling==NULL&&p->c!=s[i]) return false; u=p; } return true; } int dfs(pointer& root,int max_,int floor){ if(root->firstchild!=NULL) max_=max(max_,dfs(root->firstchild,max_,floor+1)); if(root->nextsibling!=NULL) max_=max(max_,dfs(root->nextsibling,max_,floor)); return max(max_,floor*root->tot); } int DFS(){ return dfs(root,0,0); } }; char str[10000]; int n; int main() { int T; scanf("%d",&T); while(T--){ Trie trie; scanf("%d",&n); gets(str); for(int i=0;i<n;i++){ gets(str); trie.insert(str,strlen(str)); } printf("%d\n",trie.DFS()); } }