Pagini recente » Cod sursa (job #1595069) | Cod sursa (job #1696484) | Cod sursa (job #2679690) | Cod sursa (job #684848) | Cod sursa (job #678104)
Cod sursa(job #678104)
#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_N = 2000005;
const int MAX_SOL = 1000;
char text[MAX_N];
char pattern[MAX_N];
int prefix[MAX_N];
void read() {
assert(freopen("strmatch.in", "r", stdin));
assert(freopen("strmatch.out", "w", stdout));
assert(scanf("%s", pattern + 1) == 1);
assert(scanf("%s", text + 1) == 1);
}
void compute_prefix(char* pattern) {
int n = strlen(pattern + 1);
int p = 0;
prefix[1] = 0;
for (int i = 2; i <= n; ++i) {
while (p > 0 && pattern[p + 1] != pattern[i])
p = prefix[p];
if (pattern[p + 1] == pattern[i])
++p;
prefix[i] = p;
}
}
vector<int> pattern_match(char* text, char* pattern) {
int n = strlen(text + 1), m = strlen(pattern + 1);
vector<int> matches;
int p = 0;
for (int i = 1; i <= n; ++i) {
while (p > 0 && text[i] != pattern[p + 1])
p = prefix[p];
if (text[i] == pattern[p + 1])
++p;
if (p == m) {
matches.push_back(i - m);
p = prefix[p];
}
}
return matches;
}
void write(vector<int> v) {
printf("%d\n", v.size());
for (int i = 0; i < MAX_SOL && i < (int)v.size(); ++i)
printf("%d ", v[i]);
}
int main() {
read();
compute_prefix(pattern);
write(pattern_match(text, pattern));
}