计蒜客：2019 蓝桥杯省赛 B 组模拟赛（一）程序设计：后缀字符串（字典树）

男娘i 2022-02-27 23:38 130阅读 0赞

#                                 程序设计：后缀字符串 #

### 题目链接： ###

[https://nanti.jisuanke.com/t/A2239][https_nanti.jisuanke.com_t_A2239]

一天蒜头君得到 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<=10^5暴力会超时，利用字典树，将所有的字符串倒叙存储为为一个字典树，记录每个节点出现的次数。

### 程序代码： ###

#include<stdio.h>
    #include<string.h>
    char s[100010][20];
    int ch[100010][26],v[100010];
    int sz;
    void map(char sr[],int len)
    {
    	int u,i,c;
    	u=0;
    	for(i=len-1;i>=0;i--)
    	{
    		c=sr[i]-'a';
    		if(ch[u][c]==0)
    			ch[u][c]=sz++;
    		u=ch[u][c];
    		v[u]++;
    	}
    }
    int put(char sr[],int len)
    {
    	int u,i,c;
    	u=0;
    	for(i=len-1;i>=0;i--)
    	{
    		c=sr[i]-'a';
    		u=ch[u][c];
    	}
    	return v[u];
    }
    int main()
    {
    	int n,i,len;
    	while(scanf("%d\n",&n)!=EOF)
    	{
    		sz=1;
    		memset(ch,0,sizeof(ch));
    		memset(v,0,sizeof(v));
    		for(i=1;i<=n;i++)
    		{
    			scanf("%s",s[i]);
    			len=strlen(s[i]);
    			map(s[i],len);
    		}
    		for(i=1;i<=n;i++)
    		{
    			len=strlen(s[i]);
    			printf("%d\n",put(s[i],len));
    		}
    	}
    	return 0;
    }

[https_nanti.jisuanke.com_t_A2239]: https://nanti.jisuanke.com/t/A2239