forked from yuanhui-yang/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathboyer_moore.cc
More file actions
122 lines (113 loc) · 2.72 KB
/
boyer_moore.cc
File metadata and controls
122 lines (113 loc) · 2.72 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//
// Boyer-Moore string matching
//
// Description:
// It processes a pattern string to find
// all occurrence of a given text.
//
// Algorithm:
// It matches a pattern string from the last to the front.
// If the string is random, this can skip many comparison.
//
// Complexity:
// O(n + |occur|) with O(m) preprocessing.
// In a random case, it reduced to O(n/m + |occur|).
//
// Verified:
// SPOJ 21524
//
// Comment:
// BM is often considered faster than KMP.
// However, in the programming contest setting,
// these are equally fast.
//
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <functional>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
struct boyer_moore {
int m;
const char *p;
vector<int> skip, next;
boyer_moore(const char *p) : p(p), m(strlen(p)) {
skip.resize(0x100); // bad char heuristics
for (int i = 0; i < m; ++i)
skip[p[i]] = m - i - 1;
vector<int> g(m, m); // good suffix heuristics
next.resize(m);
for (int i = 0; i < m; ++i)
next[i] = 2*m-i-1;
for (int i = m-1, j = m; i >= 0; --i, --j) {
g[i] = j;
while (j < m && p[j] != p[i]) {
next[j] = min(next[j], m-i-1);
j = g[j];
}
}
}
vector<int> match(const char s[]) {
int n = strlen(s);
vector<int> occur;
for (int i = m-1; i < n; ) {
int j = m-1;
while (j >= 0 && s[i] == p[j]) --i, --j;
if (j < 0) {
/* match at s[i+1, ..., i+m] */
occur.push_back(i+1);
i += m + 1;
} else i += max(skip[s[i]], next[j]);
}
return occur;
}
};
// for comparison
struct knuth_morris_pratt {
int m;
const char *p;
vector<int> fail;
knuth_morris_pratt(const char *p) : p(p), m(strlen(p)) {
fail.resize(m+1, -1);
for (int i = 1, j = -1; i <= m; ++i) {
while (j >= 0 && p[j] != p[i-1]) j = fail[j];
fail[i] = ++j;
}
}
vector<int> match(const char *s) {
int n = strlen(s);
vector<int> occur;
for (int i = 0, k = 0; i < n; ++i) {
while (k >= 0 && s[i] != p[k]) k = fail[k];
if (++k == m) {
/* match at s[i-m+1 ... i] */
occur.push_back(i-m+1);
}
}
return occur;
}
};
int main() {
int ncase; scanf("%d", &ncase);
for (int icase = 0; icase < ncase; ++icase) {
if (icase > 0) printf("\n");
char s[1000010], p[1000010];
scanf("%s %s", s, p);
boyer_moore M(p);
auto v = M.match(s);
if (v.empty()) {
printf("Not Found\n");
} else {
printf("%d\n", v.size());
for (int i = 0; i < v.size(); ++i) {
if (i > 0) printf(" ");
printf("%d", v[i]+1);
}
printf("\n");
}
}
}