fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string text,pattern;
  5. vector<int> nwindow;
  6.  
  7. void gen_nwindow_mapping()
  8. {
  9. 	int wsz=0;
  10. 	nwindow.resize(pattern.size(),0);
  11. 	for(int i=1;i<pattern.size();i++)
  12. 	{
  13. 		if(pattern[i]==pattern[wsz])                                //when matched
  14. 		{
  15. 			wsz++; nwindow[i]=wsz; continue;
  16. 		}
  17.  
  18. 		if(wsz==0)                                         //not matched and wsz comes to zero 
  19. 			nwindow[i]=0;	
  20. 		else
  21. 		{
  22. 				wsz=nwindow[wsz-1];i--;                   //index is not incremented 
  23. 		}
  24. 	}
  25.  
  26. }
  27.  
  28. void match_text()
  29. {
  30. 	int wsz=0;
  31. 	cout<<"pattern found at indexes : ";
  32. 	for(int i=0;i<text.size();i++)
  33. 	{
  34. 		if(text[i]==pattern[wsz])
  35. 		{	
  36. 			wsz++;	
  37.  
  38. 			if(wsz==pattern.size())
  39. 			{
  40. 				cout<<i-pattern.size()+1<<" ";
  41. 				wsz=nwindow[wsz-1];
  42. 			}
  43.  
  44. 			continue;
  45. 		}
  46.  
  47. 		if(wsz==0)continue;
  48. 		wsz=nwindow[wsz-1];
  49. 		i--;                    //i cant be incremented till there is a match or wsz comes to zero
  50.  
  51. 	}
  52. }
  53.  
  54.  
  55.  
  56.  
  57. int main() {
  58. 	cin>>text>>pattern;
  59. 	gen_nwindow_mapping();	
  60. 	match_text();	
  61. 	return 0;
  62. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
cabaababaabaac
abaabaa
stdout
copy 
pattern found at indexes : 6
https://ideone.com/n0Miwk
language:
C++14 (gcc 8.3)
created:
9 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!