fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int mod = 1000000007;
  5. int l = 26;
  6. char a = 'a';
  7. long long exp(int b, int e){
  8. 	long long a = 1;
  9. 	long long x = b;
  10. 	while(e){
  11. 		if(e%2)	a = (a*x)%mod;
  12. 		x = (x*x)%mod;
  13. 		e = e/2;
  14. 	}
  15. 	return a;
  16. }
  17. void push_back(long long &seed, int c){
  18. 	seed = (26*seed + c%l)%mod;
  19. }
  20. void pop_front(long long &seed, int c, long long x){
  21. 	x *= c%l;
  22. 	x = mod - x%mod;
  23. 	seed = (seed+x)%mod;
  24. }
  25.  
  26. vector<int> match(const string &s, const string &w){
  27. 	vector<int> p;
  28.  
  29. 	int n = w.size();
  30. 	if(!n)	return p;
  31.  
  32. 	int h_minus = exp(l,n-1);
  33.  
  34. 	long long h = 0;
  35. 	for(char c: w)	push_back(h,c-a);
  36. 	cout<<"Hash value of the word: "<<h<<endl;
  37.  
  38. 	if(s.size()<n)	return p;
  39. 	int i=0;
  40. 	long long x=0;
  41. 	while(i<n)	push_back(x,s[i++]-a);
  42. 	if(h==x)	p.push_back(i-n);
  43.  
  44. 	while(i<s.size()){
  45. 		pop_front(x,s[i-n]-a,h_minus);
  46. 		push_back(x,s[i++]-a);
  47. 		if(h==x)	p.push_back(i-n);
  48. 	}
  49. 	return p;
  50. }
  51. int main() {
  52. 	string s;
  53. 	string w;
  54. 	cin>>s>>w;
  55. 	vector<int> ans = match(s,w);
  56. 	cout<<"The given word is matched in the string at following positions:"<<endl;
  57. 	for(int x: ans)	cout<<x<<' ';
  58. 	cout<<endl;
  59. 	cout<<s<<endl;
  60. 	int j=0;
  61. 	for(int i=0; i<s.size()&&j<ans.size(); i++){
  62. 		if(i==ans[j]&&++j)	cout<<'^';
  63. 		else	cout<<' ';
  64. 	}
  65. 	cout<<endl;
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 4168KB
comments ()
stdin
copy 
abcdabcdabcdab
abcdabcd
stdout
copy 
Hash value of the word: 334050187
The given word is matched in the string at following positions:
0 4 
abcdabcdabcdab
^   ^
https://ideone.com/8rv2vs
string matching, needle in haystack. Using hash technique.
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!