最近在搞搞Trie,写篇博客总结一下吧.
Trie就是将字符串的每个字符用树的边储存,查询时只要沿着根节点往下爬。
Trie的根节点为空,表示空串.
----------------------------------------------------------------------------------------------------
在详细的操作前,我们先了解一下几个数组。
trie[u][c]=x表示编号为u的节点的第c个孩子编号为x.
这里的编号有两个含义,u,x表示字符插入trie时的顺序编号,c表示这个字符在其字符集中的编号(如a表示1,b表示2....)
f[u]表示这个插入的单词是否以u结尾。
如图
u,x为红色标号,c为蓝色编号
Trie具体上有两个操作:
插入
1 void insert(char *s) { 2 3 int u=1; int len=strlen(s); //u=1表示根节点 4 5 for (int i=0;i<len;i++){ 6 7 int c=s[i]-'a';//计算c编号 8 9 if (!trie[u][c]) trie[u][c]=++tot;//如果字符未出现则插入 10 11 u=trie[u][c];//根节点指向下一位 12 13 } 14 15 f[u]=true;//给单词末尾打上标记 16 17 }
查询
1 bool find(char *s) 2 { 3 int u=1; 4 int len=strlen(s); 5 for (int i=0;i<len;i++){ 6 int c=s[i]-'a'; 7 if (!trie[u][c]) { 8 return false;//查询单词是否出现 9 break; 10 } 11 u=trie[u][c]; 12 } 13 return true; 14 }
查询操作中我们也可以添加数组查询前缀个数等等,但大体思路都是沿着根往下查询统计.
----------------------------------------------------------------------------------------------------
题目练习:
入门模版题,查询前缀。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <cmath> 7 #define ll long long 8 #define out(a) printf("%d",a) 9 #define writeln printf(" ") 10 using namespace std; 11 int trie[1000050][50]; 12 bool f[1000050]; 13 char s1[1000050],s2[1000050]; 14 int tot=0; 15 int n,m; 16 int read() 17 { 18 int s=0,t=1; char c; 19 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 20 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 21 return s*t; 22 } 23 ll readl() 24 { 25 ll s=0,t=1; char c; 26 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 27 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 28 return s*t; 29 } 30 void insert(char *s) 31 { 32 int len=strlen(s); 33 int u=1; 34 for (int i=0;i<len;i++){ 35 int c=s[i]-'a'; 36 if (!trie[u][c]) trie[u][c]=++tot; 37 u=trie[u][c]; 38 } 39 f[u]=true; 40 } 41 bool find(char *s) 42 { 43 int len=strlen(s); 44 int u=1; 45 for (int i=0;i<len;i++){ 46 int c=s[i]-'a'; 47 if (!trie[u][c]) return false; 48 u=trie[u][c]; 49 } 50 return true; 51 } 52 int main() 53 { 54 n=read(); 55 for (int i=1;i<=n;i++){ 56 scanf("%s",s1); 57 insert(s1); 58 } 59 m=read(); 60 for (int i=1;i<=m;i++){ 61 scanf("%s",s2); 62 if (find(s2)) puts("YES"); 63 else puts("NO"); 64 } 65 return 0; 66 } 67
找s,t使得其中一个是另一个的前缀。
n2的复杂度是过不了的。
考虑在读入的时候查询,如果一条链上有新的节点插入,说明有前缀。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <cmath> 7 #define ll long long 8 #define out(a) printf("%d ",a) 9 #define writeln printf(" ") 10 #define max(a,b) a>b?a:b 11 #define min(a,b) a<b?a:b 12 using namespace std; 13 int n,m; 14 int tot; 15 int trie[100050][26]; 16 char str[100050]; 17 bool f[100050],ff; 18 int read() 19 { 20 int s=0,t=1; char c; 21 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 22 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 23 return s*t; 24 } 25 ll readl() 26 { 27 ll s=0,t=1; char c; 28 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 29 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 30 return s*t; 31 } 32 bool find(char *s) 33 { 34 int u=1; bool flag=false; 35 int len=strlen(s); 36 for (int i=0;i<len;i++){ 37 int c=s[i]-'0'; 38 if (!trie[u][c]) trie[u][c]=++tot; 39 else if (i+1==len) flag=true; 40 u=trie[u][c]; 41 if (f[u]) flag=true; 42 } 43 f[u]=true; 44 return flag; 45 } 46 int main() 47 { 48 n=read(); 49 for (int i=1;i<=n;i++){ 50 m=read(); tot=1; 51 memset(trie,0,sizeof(trie)); 52 memset(f,false,sizeof(f)); ff=false; 53 for (int j=1;j<=m;j++){ 54 scanf("%s",str); 55 if (find(str)) ff=true;//,out(j),writeln; 56 } 57 if (ff) puts("NO"); 58 else puts("YES"); 59 } 60 return 0; 61 }
模版题++
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <cmath> 7 #define ll long long 8 #define out(a) printf("%d",a) 9 #define writeln printf(" ") 10 #define min(a,b) a<b?a:b 11 #define max(a,b) a>b?a:b 12 using namespace std; 13 int n,m; 14 int tot; 15 char s[100050]; 16 int trie[500050][26],a[500050]; 17 bool f[500050],flag[500050]; 18 string ans; 19 int read() 20 { 21 int s=0,t=1; char c; 22 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 23 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 24 return s*t; 25 } 26 ll readl() 27 { 28 ll s=0,t=1; char c; 29 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 30 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 31 return s*t; 32 } 33 void insert(char *s) 34 { 35 int u=1; 36 int len=strlen(s); 37 for (int i=0;i<len;i++){ 38 int c=s[i]-'a'; 39 if (!trie[u][c]) trie[u][c]=++tot; 40 u=trie[u][c]; 41 } 42 f[u]=true; 43 } 44 void find(char *s) 45 { 46 int u=1; bool ff=false; 47 int len=strlen(s); 48 for (int i=0;i<len;i++){ 49 int c=s[i]-'a'; 50 if (!trie[u][c]) { 51 ans="WRONG"; ff=true; 52 break; 53 } 54 u=trie[u][c]; 55 } 56 if (not ff) { 57 if (f[u]&&flag[u]) ans="OK"; 58 else if (f[u]&¬ flag[u]) ans="REPEAT"; 59 if (ans=="OK") flag[u]=false; 60 } 61 } 62 int main() 63 { 64 n=read(); tot=1; memset(f,false,sizeof(f)); 65 memset(flag,true,sizeof(flag)); 66 memset(a,0,sizeof(a)); 67 for (int i=1;i<=n;i++){ 68 scanf("%s",s); 69 insert(s); 70 } 71 m=read(); 72 for (int i=1;i<=m;i++){ 73 scanf("%s",s); 74 find(s); 75 cout<<ans; writeln; 76 } 77 return 0; 78 }
4.洛谷 P2922 [USACO08DEC]秘密消息Secret Message
计算查询串为给定串前缀与查询串为当前串前缀的和。
插入字符串时给每个节点标记有多少个单词经过存在数组a,标记每个单词结尾的节点存在数组b.
考虑给定串为查询串前缀,那么沿着查询串往下走,如果当前节点u为某个单词终点就ans++;
考虑查询串为给定串前缀,那么给定串必然经过查询串不能再向下走的那个节点,所以ans+=a[u];但当两种情况都出现时,情况1会被重复计算,所以情况2,ans+=a[u]-b[u];
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <cmath> 7 #define ll long long 8 #define out(a) printf("%d",a) 9 #define max a>b?a:b 10 #define min a<b?a:b 11 #define writeln printf(" ") 12 #define N 500050 13 using namespace std; 14 int n,m; 15 int tot,ans; 16 int trie[N][2],a[N],b[N]; 17 bool f[N]; 18 int read() 19 { 20 int s=0,t=1; char c; 21 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 22 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 23 return s*t; 24 } 25 ll readl() 26 { 27 ll s=0,t=1; char c; 28 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 29 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 30 return s*t; 31 } 32 void insert() 33 { 34 int u=1,k,x; 35 k=read(); 36 for (int i=1;i<=k;i++){ 37 x=read(); 38 if (!trie[u][x]) trie[u][x]=++tot; 39 u=trie[u][x]; a[u]++; 40 } 41 f[u]=true; b[u]++; 42 } 43 void find() 44 { 45 int u=1,k,x; 46 bool flag=true; 47 k=read(); 48 for (int i=1;i<=k;i++){ 49 x=read(); 50 if (flag) { 51 if (!trie[u][x]) { 52 flag=false; 53 } 54 u=trie[u][x]; 55 ans+=b[u]; 56 } 57 } 58 if (flag) ans+=a[u]-b[u]; 59 } 60 int main() 61 { 62 m=read(),n=read(); tot=1; 63 for (int i=1;i<=m;i++) 64 insert(); 65 for (int i=1;i<=n;i++){ 66 ans=0; 67 find(); 68 out(ans); writeln; 69 } 70 return 0; 71 }
5.Codeforces 706D. Vasiliy's Multiset
一个序列最开始只有一个0,可以插入,删除数组,查询数字x与序列中数的异或最大值.
经典01trie问题.
删除操作就和插入一样修改一下标记..
查询贪心按相反的位往下爬。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <cmath> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%d",a) 10 #define writeln printf(" ") 11 #define N 6000050 12 using namespace std; 13 char c; 14 int n,x; 15 int trie[N][2],cnt[N],tot; 16 int read() 17 { 18 int s=0,t=1; char c; 19 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 20 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 21 return s*t; 22 } 23 ll readl() 24 { 25 ll s=0,t=1; char c; 26 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 27 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 28 return s*t; 29 } 30 void insert(int x) 31 { 32 int u=1; 33 for (int i=31;i>=0;i--){ 34 int c=((1<<i)&x)>0; //out(c); writeln; 35 if (!trie[u][c]) trie[u][c]=++tot; 36 u=trie[u][c]; 37 cnt[u]++; 38 } 39 } 40 void deleted(int x) 41 { 42 int u=1; 43 for (int i=31;i>=0;i--){ 44 int c=((1<<i)&x)>0; 45 u=trie[u][c]; 46 cnt[u]--; 47 } 48 } 49 int find(int x) 50 { 51 int ans=0; 52 int u=1; 53 for (int i=31;i>=0;i--){ 54 int c=((1<<i)&x)>0; 55 if (cnt[trie[u][1-c]]) { 56 ans+=1<<i; 57 u=trie[u][1-c]; 58 } 59 else u=trie[u][c]; 60 } 61 return ans; 62 } 63 int main() 64 { 65 n=read(); tot=1; 66 insert(0); 67 for (int i=1;i<=n;i++){ 68 c=getchar(); 69 x=read(); 70 if (c=='+') insert(x); 71 if (c=='-') deleted(x); 72 if (c=='?') out(find(x)),writeln; 73 } 74 return 0; 75 }
6.Codeforces 714C. Sonya and Queries
一个空数组,兹磁插入,删除,查询每个位的奇偶性相同的数的个数(长度不同的补前导0)
由于这题正着插入会有很多麻烦的问题,我们考虑把数倒着插入,然后前面补0到20位,然后就是从根节点向下查询了。
难得的1A。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <cmath> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%d ",a) 10 #define writeln printf(" ") 11 #define N 6000050 12 using namespace std; 13 char c[N],cc,s[N]; 14 int n,x; 15 int trie[N][2],cnt[N],tot,f[N]; 16 int read() 17 { 18 int s=0,t=1; char c; 19 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 20 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 21 return s*t; 22 } 23 ll readl() 24 { 25 ll s=0,t=1; char c; 26 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 27 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 28 return s*t; 29 } 30 void insert(char *s) 31 { 32 int u=1; int len=strlen(s); 33 for (int i=len-1;i>=0;i--){ 34 int c=(s[i]-'0')%2; 35 if (!trie[u][c]) trie[u][c]=++tot; 36 u=trie[u][c]; cnt[u]++; 37 } 38 for (int i=1;i<=19-len;i++){ 39 int c=0; 40 if (!trie[u][c]) trie[u][c]=++tot; 41 u=trie[u][c]; cnt[u]++; 42 } 43 f[u]++; 44 } 45 void deleted(char *s) 46 { 47 int u=1; int len=strlen(s); 48 for (int i=len-1;i>=0;i--){ 49 int c=(s[i]-'0')%2; 50 u=trie[u][c]; 51 cnt[u]--; 52 } 53 for (int i=1;i<=19-len;i++){ 54 int c=0; 55 u=trie[u][c]; cnt[u]++; 56 } 57 f[u]--; 58 } 59 int find(char *s) 60 { 61 int ans=0; 62 int u=1; int len=strlen(s); 63 for (int i=len-1;i>=0;i--){ 64 int c=s[i]-'0'; 65 if (cnt[trie[u][c]]) u=trie[u][c]; 66 } 67 for (int i=1;i<=19-len;i++){ 68 int c=0; 69 if (cnt[trie[u][c]]) u=trie[u][c]; 70 } 71 ans+=f[u]; 72 return ans; 73 } 74 int main() 75 { 76 n=read(); tot=1; 77 for (int i=1;i<=n;i++){ 78 scanf("%s%s",c,s); 79 if (c[0]=='+') insert(s); 80 if (c[0]=='-') deleted(s); 81 if (c[0]=='?') out(find(s)),writeln; 82 } 83 return 0; 84 }
.......