|
一天蒜头君得到 n个字符串 si，每个字符串的长度都不超过 10。
蒜头君在想，在这 n 个字符串中，以 si 为后缀的字符串有多少个呢？
输入格式
第一行输入一个整数 n。
接下来 n 行，每行输入一个字符串 si。
输出格式
输出 n 个整数，第 i个整数表示以 si 为后缀的字符串的个数。
数据范围
对于 50% 的数据，1<=n <=10^3。
对于 100% 的数据，1<=n <=10^5。
所有的字符串仅由小写字母组成。
样例输入
3
ba
a
aba
样例输出
2
3
1
题意描述：求在这 n 个字符串中，以 si 为后缀的字符串有多少个。
分析：其实这道题可以变换一下把后缀换成前缀，怎样实现呢，就是让输入的数组反转一下，然后问题就变为以 si 为后缀的字符串有多少个，现在这道题就跟HDU上的统计难题的思路差不多了，算法实现：建立字典树。
代码如下：
#include<stdio.h>
#include<string.h>
#include<ctype.h>
char str[100005][11];
struct node//定义结构体
{
int number;
node *next[26];
node()//初始化节点
{
number=0;//个数清零
memset(next,0,sizeof(next));//指针数组清零
}
};
node *root=NULL;//定义根节点
void build(char s[],int len)//建立字典树函数
{
node *p=root;//把根节点赋给p
int i;
for(i=0;i<len;i++)//循环遍历字符数组s
{
if(p->next[s[i]-'a']==NULL)//如果目前节点为空，则建立新节点存储这个字符
{
p->next[s[i]-'a']=new node;
}
p=p->next[s[i]-'a'];//把p指向p->next[s[i]-'a']
p->number++;//以当前结点为前缀的单词个数+1
}
}
int search(int j,int len)//查找字典树函数
{
node *p=root;//把根节点赋给p
int i;
for(i=0;i<len;i++)//循环遍历字符数组str
{
if(p->next[str[j][i]-'a']==NULL)//走到字典树的叶子节点该单词str还没结束，以该串为前缀的单词数为0
{
return 0;
}
p=p->next[str[j][i]-'a'];//指向下一个节点
}
return p->number; //返回以str为前缀的单词个数
}
int main()
{
int n,len,i=1,k,j,count;
char s[11],s1[11];
root=new node;//生成根节点
memset(str,0,sizeof(str));
scanf("%d",&n);
getchar();
while(n--)
{
gets(s1);
len=strlen(s1);
for(k=0;k<len;k++)
s[k]=s1[len-1-k];//反转字符串，使其把问题由后缀变为前缀
s[len]='\0';
strcpy(str[i],s);
i++;
len=strlen(s);
build(s,len);//建立字典树函数
}
j=1;
while(j<i)
{
len=strlen(str[j]);
count=search(j,len);//查找字典树函数
printf("%d\n",count);
j++;
}
return 0;
}
| 
转播
