fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN=300000;
  4. const int P=31;
  5. const int MOD=1e9+7;
  6. int pow_P[MAXN+7];
  7. int h[MAXN+7];
  8. int h_rev[MAXN+7];
  9.  
  10.  
  11. void powing(int n){
  12. 	pow_P[0]=1;
  13. 	for(int i=1;i<=n;i++){
  14. 		pow_P[i]=((long long)P*pow_P[i-1])%MOD;	
  15. 	}
  16. }
  17. void hashing(string s,int n){
  18. 	h[0]=((long long)s[0]*pow_P[0]+MOD)%MOD;
  19. 	for(int i=1;i<n;i++){
  20. 		h[i]=(h[i-1]+(long long)s[i]*pow_P[i]+MOD)%MOD;
  21. 	}
  22. }
  23. void hashing_rev(string s,int n){
  24. 	h_rev[0]=((long long)s[n-1]*pow_P[0]);
  25. 	for(int i=2;i<n-1;i++){
  26. 		h_rev[i-1]=(h_rev[i-2]+(long long)s[n-i]*pow_P[i-1]+MOD)%MOD;
  27. 	}
  28. }
  29. int main() {
  30. 	int n;cin>>n;
  31. 	string s,s_rev;cin>>s>>s_rev;
  32. 	powing(n);
  33. 	hashing(s,n);
  34. 	hashing_rev(s_rev,n);
  35. 	cout<<h[0]<<" "<<h[1]<<endl;
  36. 	cout<<h_rev[0]<<" "<<h_rev[1]<<endl;
  37. 	cout<<pow_P[0]<<" "<<pow_P[1]<<" "<<pow_P[2]<<endl;
  38. 	cout<<h_rev[2-1]<<'='<<h_rev[2-2]<<"+"<<s_rev[n-2]<<"*"<<pow_P[2-1]<<endl;
  39. 	return 0;
  40. }
Success #stdin #stdout 0s 5564KB
comments (?)
stdin
copy 
5
xyzee
eezyx
stdout
copy 
120 3871
120 3871
1 31 961
3871=120+y*31
https://ideone.com/QktYid
language:
C++ (gcc 8.3)
created:
118 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!