-
Notifications
You must be signed in to change notification settings - Fork 0
/
104. SearchPattern(Raben-karp).cpp
64 lines (50 loc) · 1.19 KB
/
104. SearchPattern(Raben-karp).cpp
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
#define MOD 1000000007
long long modPower(long long a, long long b)
{
if (b == 0)
return 1;
long long p = modPower(a, b / 2);
if (b % 2 == 1)
return p * p % MOD * a % MOD;
return p * p % MOD;
}
vector<int> stringMatch(string text, string pattern)
{
int n = text.size();
int m = pattern.size();
vector<int> ans;
long long maxPow = modPower(26, m - 1);
long long hp = 0, ht = 0;
for (int i = 0; i < m; i++){
hp = hp * 26 + pattern[i] - 'a';
hp %= MOD;
}
for (int i = 0; i < m - 1; i++)
{
ht = ht * 26 + text[i] - 'a';
ht %= MOD;
}
for (int i = 0; i <= n - m; i++)
{
ht = ht * 26 + text[i + m - 1] - 'a';
ht %= MOD;
if (ht == hp)
{
bool match = true;
for (int j = 0; j < m; j++){
if (text[i + j] != pattern[j]){
match = false;
break;
}
}
if (match)
{
ans.push_back(i + 1);
}
}
ht = ht - maxPow * (text[i] - 'a');
ht %= MOD;
ht = (ht + MOD) % MOD;
}
return ans;
}