萌新求调链式前向星的字符串hash
  • 板块学术版
  • 楼主zhaozeyao_____
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/8/26 09:19
  • 上次更新2023/11/3 01:10:07
查看原帖
萌新求调链式前向星的字符串hash
1034701
zhaozeyao_____楼主2023/8/26 09:19
#include<bits/stdc++.h>
using namespace std;

const int N = 10010,base = 31,mod = 10009;

struct node
{
	string to;
	int nxt;
}e[N];

int head[N],tot;

int hsh(string s)
{
	int cnt = 0;
	for(int i = 0;i<s.size();i++)
	{
		cnt = (cnt * base + s[i]) % mod;
	}
	int q = head[cnt];
	while(q!=0)
	{
		if(e[q].to==s)
		{
			return q;
		}
		q = e[q].nxt;
	}
	if(q==0)
	{
		e[++tot].to = s;
		head[cnt] = tot;
		e[tot].nxt = head[cnt];
	}
	return tot;
}

int findd(string s)
{
	int cnt = 0;
	for(int i = 0;i<s.size();i++)
	{
		cnt = (cnt * base + s[i]) % mod;
	}
	int q = head[cnt];
	while(q!=0)
	{
		if(e[q].to==s)
		{
			return q;
		}
		q = e[q].nxt;
	}
	return q;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		string h;
		cin>>h;
		int m = hsh(h);
	}
	cout<<tot<<endl; 
} 
2023/8/26 09:19
加载中...