1 #include <vector> 2 #include <list> 3 #include <map> 4 #include <set> 5 #include <queue> 6 #include <deque> 7 #include <stack> 8 #include <bitset> 9 #include <algorithm>10 #include <functional>11 #include <numeric>12 #include <utility>13 #include <sstream>14 #include <iostream>15 #include <iomanip>16 #include <cstdio>17 #include <cmath>18 #include <cstdlib>19 #include <ctime>20 #include <cstring>21 #include <string>22 23 using namespace std;24 25 #define sz(a) int((a).size())26 #define pb push_back27 28 29 class BoyerMoore {30 private:31     int R;32     string pat;33     vector<int> right;     // the bad-character skip array34 35 public:36     BoyerMoore(string _pat, int _R = 256) {37         pat = _pat;38         R = _R;39         right = vector<int> (R, -1);40         41         for (int i = 0; i < sz(pat); ++i) {42             right[pat[i]] = i;43         }44     }45     46     47     // return offset of first match; -1 if no match48     int search(string txt) {49         int M = sz(pat);50         int N = sz(txt);51         int skip;52         for (int i = 0; i <= N - M; i += skip) {53             skip = 0;54             for (int j = M-1; j >= 0; j--) {55                 if (pat[j] != txt[i+j]) {56                     skip = max(1, j - right[txt[i+j]]);57                     break;58                 }59             }60             if (skip == 0) return i;    // found61         }62         return -1;                       // not found63     }64 65 };66 67 68 int main() {69     string txt, pat;70     cin >> txt;71     cin >> pat;72     73     BoyerMoore *obj = new BoyerMoore(pat);74     int pos = obj->search(txt);75     76     cout << pos << endl;77     78     79     delete obj;80     return 0;81 }