很“简单”的Trie树
前缀统计
可以求出对于所有的串 有多少是string str
的前缀
如果边做边查询 貌似会出bug 可能是我太菜了
所以把所有的插入进去在查询
那么……就要注意一下Root -> search(Root,str[i]) > 1
因为自己肯定是自己的前缀awa
如果你用指针写的 请delete或者free一下
不然的话
有甚么困难都可以看看代码
Author : Miku_𝓜𝓪𝓼𝓽𝓮𝓻
Date : 2021/5/29
#include <bits/stdc++.h>
using namespace std;
typedef long long LL ;
typedef pair<int,int> pii ;
int read() {
int x = 0 ; bool f = false ; char ch = getchar() ;
for (;!isdigit(ch);ch = getchar()) f |= (ch == '-') ;
for (;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48) ;
return f ? ~ x + 1 : x ;
}
const int M = 1e4 + 5 , N = 1e1 + 5 ;
int T , n ;
bool fl ;
char str[M][N] ;
class Trie {
private :
int Tp , value_type ;
Trie *son[10] ;
public :
Trie(int x):Tp(x){
for (int i = 0 ; i < 10 ; ++i ) son[i] = NULL ;
}
void insert(Trie* &Root,char str[]) {
int len = strlen(str) ;
Trie* p = Root ;
for (int i = 0 ; i < len ; ++i ) {
int num = str[i] - '0' ;
if (p -> son[num] == NULL) {
p -> son[num] = new Trie(0) ;
p -> son[num] -> value_type = num ;
}
p = p -> son[num] ;
}
++ p -> Tp ;
}
int search(Trie* &Root,char str[]) {
int len = strlen(str) , ans = 0 ;
Trie* p = Root ;
for (int i = 0 ; i < len ; ++i ) {
int num = str[i] - '0' ;
if (p -> son[num] == NULL) return ans ;
p = p -> son[num] ;
ans += p -> Tp ;
} return ans ;
}
void del(Trie* &Root) {
for (int i = 0 ; i < 10 ; ++i )
if (Root -> son[i] != NULL) del(Root -> son[i]) ;
delete(Root) ;
}
} ;
signed main() {
T = read() ;
while (T --) {
n = read() , fl = true ;
Trie* Root = new Trie(0) ;
for (int i = 1 ; i <= n ; ++i ) {
scanf("%s",str[i]) ;
Root -> insert(Root,str[i]) ;
}
for (int i = 1 ; i <= n ; ++i )
if (Root -> search(Root,str[i]) > 1) fl = false ;
puts(fl ? "YES" : "NO") ;
Root -> del(Root) ;
}
}