刚学的哈希 只过了30 大佬们帮忙看看TT
查看原帖
刚学的哈希 只过了30 大佬们帮忙看看TT
1055881
DangX楼主2024/7/20 20:35
#include<bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  typedef unsigned long long ULL;
  #include <string>
  // 解题思路: 
  
  const int N=1e5+5; // 字符串数量上界
  const int M=1.5e3+10; // 单个字符串最大长度
  const int P=131; // 131,13331不容易哈希碰撞
  
  // h[i]:表示s[1~i]的哈希值,如h[2]表示字符串s前两个字符组成字符串的哈希值
  ULL p[N],h[N];
  char s[M]; // 存储字符串
  int n;
  // 计算字符串s的哈希值
  ULL Hash(char str[]) {
  	h[0]=0; // 空串哈希值为0
  	int len=strlen(str); // 计算长度
  	for(int i=1;i<=len;i++) {
  		h[i]=h[i-1]*P+str[i-1];	
  	}
  	return h[len]; // 返回此串的哈希值
  }
 
 // 预处理hash函数的前缀和,时间复杂度O(n)
 void init() {
 	// p^0=1,空串哈希值为0
 	p[0]=1,h[0]=0;
 	for(int i=1;i<=n;i++) {
 		p[i]=p[i-1]*P;	
 		h[i]=h[i-1]*P+s[i-1]; // 前缀和计算公式
 	}
 }
int a[2002],b[2002];map<ll,ll>mp[1000005];char m[M];int cnt=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s>>m;
		init();
		a[i]=h[2];
		b[i]=Hash(m);
		int a1=a[i],b1=b[i];
		if(b1!=a1){
			cnt+=mp[a1][b1];
			mp[b1][a1]++;
		}
	}
	cout<<cnt;
	
	return 0;
}
2024/7/20 20:35
加载中...