求大佬看看吗,用Trie树写,数据小了会RE3个点 数据大了就爆内存了
查看原帖
求大佬看看吗,用Trie树写,数据小了会RE3个点 数据大了就爆内存了
575975
wuliu楼主2022/1/30 15:16
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;
const int N=150000;

int son[N][128],cnt[N],idex;
string s;

void insert(string c)
{
	int p=0;
	
	
	for(int i=0;i<s.size();i++)
	{
		int u;
		if(s[i]<=57&&s[i]>=48)
		{
			u=s[i]-0;
			
		}else if(s[i]<=122&&s[i]>=97)
		{
			u=s[i]-'a';
		}else if(s[i]>=65&&s[i]<=90)
		{
			u=s[i]-0;
			//cout<<u<<endl;
		}
		
		if(!son[p][u])son[p][u]=++idex;
		p=son[p][u];
		//cout<<p<<endl;
		
	}
	cnt[p]++;
}
int main()
{
	int m;
	scanf("%d",&m);
	//int n=m;
	while(m--)
	{
		cin>>s;
		insert(s);
		
	}
	int ans=0;
	for(int i=0;i<N;i++)
	{
		if(cnt[i]!=0)ans++;
	}
	printf("%d",ans); 
	return 0;
}
2022/1/30 15:16
加载中...