fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mod 1000000007
  4. #define int long long
  5. #define pii pair<int,int>
  6. #define mii map<int,int>
  7. #define uii unordered_map<int,int>
  8. #define si set<int>
  9. #define usi set<int>
  10. #define pb push_back
  11. #define mp make_pair
  12. int32_t main(){
  13. 	string s;
  14. 	cin >> s;
  15. 	int n = s.size();
  16. 	int p = 31;
  17. 	vector<int> p_pow(n+1,1);
  18. 	vector<int> hash(n+1,0);
  19. 	for(int i=1;i<=n;i++)
  20. 		p_pow[i] = (p_pow[i-1] * p)%mod;
  21. 	for(int i=1;i<=n;i++){
  22. 		int v;
  23. 		if(s[i-1] >= 'A' && s[i-1] <= 'Z'){
  24. 			v = s[i-1] - 'A' + 1;
  25. 		}else{
  26. 			v = s[i-1] - 'a' + 1;
  27. 		}
  28. 		hash[i] = (hash[i-1] + (v) * p_pow[i-1])%mod;
  29. 	}
  30. 	int q;
  31. 	cin >> q;
  32. 	while(q--){
  33. 		string m;
  34. 		cin >> m;
  35. 		int a_hash = 0;
  36. 		for(int i=0;i<m.size();i++){
  37. 			int v;
  38. 			if(m[i] >= 'A' && m[i] <= 'Z'){
  39. 				v = m[i] - 'A' + 1;
  40. 			}else{
  41. 				v = m[i] - 'a' + 1;
  42. 			}
  43. 			a_hash = (a_hash + (v) * p_pow[i])%mod;
  44. 		}
  45. 		bool flag = true;
  46. 		for(int i=1;i<=(n-m.size()+1);i++){
  47. 			int curr_hash = (hash[i+m.size()-1] - hash[i-1] + mod)%mod;
  48. 			if(curr_hash == (a_hash * p_pow[i-1])%mod){
  49. 				cout << "Y\n";
  50. 				flag = false;
  51. 				break;
  52. 			}
  53. 		}
  54. 		if(flag) cout << "N\n";
  55. 	}
  56. }
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oRX1SS
language:
C++ (gcc 8.3)
created:
3 years 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!