RobinKrap.cpp

#include<bits/stdc++.h>
using namespace std;
int p=31;
const int N=1e5+3, m=1e9+7;
vector<long long> powers(N);
long long calculate_hash(string s){
	long long hash=0;
	for(int i=0;i<s.size();i++){
		hash = (hash + (s[i]-'a'+1)*powers[i])%m;
	}
	return hash;
}
int main(){
	powers[0]=1;
	for(int i=1;i<N;i++){
		powers[i]=(powers[i-1]*p)%m;
	}
	vector<string> string = {"aa", "ab", "aa", "b", "cc", "aa"};
	vector<long long> hashes;
	for(auto w : string){
		hashes.push_back(calculate_hash(w));
	}
	sort(hashes.begin(),hashes.end());
	int distinct = 0;
	for(int i=0;i<hashes.size();i++){
		if(i==0 or hashes[i]!=hashes[i-1]){
			distinct++;
		}
	}
	cout<<distinct<<"\n";
}
// 	sort(string.begin(), string.end()); //o(nmlog(n))
// 	int distinct = 0;
// 	for(int i=0;i<string.size();i++){
// 		if(i==0 or string[i]!=string[i-1]){
// 			distinct++;
// 		}
// 	}
// 	cout<<distinct<<"\n";
// }