fork(2) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. void makeBC(int* bc,string pat)		{
  6.  
  7. 	for(int i = 0; i <= 255; i++)
  8. 		bc[i] = -1;
  9.  
  10. 	for(int i = 0; i < pat.length(); i++)	
  11. 		bc[pat[i]] = i;
  12. }
  13.  
  14. void makeF(int* f,int* s,string pat)	{
  15.  
  16. 	int m = pat.length();
  17. 	for(int k = 0; k <= m; k++)	
  18. 		s[k] = 0;
  19.  
  20. 	int i = m, j = m+1;
  21. 	f[i] = j;
  22.  
  23. 	while(i > 0)	{
  24.  
  25. 		while(j <= m && pat[i-1] != pat[j-1])	{
  26.  
  27. 			if(s[j] == 0)
  28. 				s[j] = j-i;
  29. 			j = f[j];
  30. 		}
  31. 		i--;
  32. 		j--;
  33. 		f[i] = j;
  34. 	}
  35.  
  36.  
  37. }
  38.  
  39. void makeS(int* f,int* s,string pat)	{
  40.  
  41. 	int m = pat.length();
  42. 	int j = f[0];
  43.  
  44. 	for(int i = 0; i <= m; i++)	{
  45.  
  46. 		if(s[i] == 0)
  47. 				s[i] = j;
  48.  
  49. 		if(i == j)
  50. 				j = f[j];
  51. 	}
  52.  
  53.  
  54. }
  55.  
  56. void BM(string text, string pat)	{
  57.  
  58. 	int m = pat.length();
  59. 	int n = text.length();
  60. 	int bc[256]; //array bad character
  61. 	int f[m+1]; //F function preprocess contained the starting 
  62. 				//position of the widest border of the suffix 
  63. 				//of the pattern beginning at position i.
  64. 	int s[m+1]; //Mảng s này người ta nói là lưu khoảng cách dịch chuyển
  65. 				//lớn nhất có thể.
  66.  
  67. 	//make preprocess
  68. 	makeBC(bc,pat);
  69. 	makeF(f,s,pat);
  70. 	makeS(f,s,pat);
  71.  
  72. 	//search
  73. 	int i = 0,j;
  74.  
  75. 	while(i <= m-n)	{
  76.  
  77. 		j = m-1;
  78. 		while(j >= 0 && pat[j] == text[i+j])
  79. 			j--;
  80.  
  81. 		if(j < 0)	{
  82.  
  83. 			cout << "Found pattern at index: " << i << endl;
  84. 			i += s[0];
  85. 		}
  86. 		else
  87. 			i += std::max(s[j+1], j - bc[text[i+j]]);
  88. 	}
  89.  
  90. }
  91.  
  92. int main()	{
  93.  
  94. 	string text = "abcababacbabbababcbcab";
  95. 	string pat = "abbabab";
  96.  
  97. 	BM(text,pat);
  98. 	return 0;
  99. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4EHuRB
language:
C++14 (gcc 8.3)
created:
11 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!