题目
题意分析:
这道题目就是一道Trie树相关操作的题目(这道题目只涉及了插入操作),求最少的结点数目就相当于输出向Trie树中插入的最后一个结点的序号(注意开始就有根结点)
做题思路:
按照Trie树的模板来做即可
代码实现
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5+5;
char s[100];
ll sum=1;
int trie[maxn][70]; //这里是int类型,不是char类型,同时十足要开的大一些
void insert()
{
int len=strlen(s);
int root=0,i;
for(i=0;i<len;i++)
{
int u=s[i]-'A';
if(!trie[root][u])
{
trie[root][u]=++sum;
}
root=trie[root][u];
}
}
int main()
{
//while(gets(s))
while(~scanf("%s",s))
{
insert();
}
cout<<sum<<endl;
return 0;
}