这是我的代码:
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
using namespace std;
struct trie {
int nex[100000][26], cnt;
bool exist[1000000];//该结点结尾的字符串是否存在
void insert(char *s, int l) {//插入字符串
int p = 0;
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
if (!nex[p][c]) {
nex[p][c] = ++cnt;
}
p = nex[p][c];
exist[p]+=1;
}
}
bool find(char *s, int l) {//查找字符串
int p = 0;
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
if (!nex[p][c]) return 0;
p = nex[p][c];
}
return exist[p];
}
};
trie tri;
char str[23];
int len;
int main() {
while (gets(str)) {
len = strlen(str);
if (len == 0) break;
tri.insert(str, len);
}
while (gets(str)) {
len = strlen(str);
printf("%d\n", tri.find(str, len));
}
return 0;
}
这是别人的代码:
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=500000;
char wen[20];
struct node{
int tot;
int child[26];
node(){
tot=0;
memset(child,0,sizeof(child));
}
}tree[maxn];
int sz=0;
void insert(char *s){
int u=0;
int h=strlen(s);
for(int i=0;i<h;i++){
int pos=s[i]-'a';
if(tree[u].child[pos]==0){
tree[u].child[pos]=++sz;
}
u=tree[u].child[pos];
tree[u].tot++;
}
}
int find(char *t){
int u=0;
int h=strlen(t);
for(int i=0;i<h;i++){
int pos=t[i]-'a';
if(tree[u].child[pos]==0){
return 0;
}
u=tree[u].child[pos];
}
return tree[u].tot;
}
int main(){
while(gets(wen)){
if(strlen(wen)==0) break;
insert(wen);
}
while(gets(wen)){
printf("%d\n",find(wen));
}
return 0;
}