Pagini recente » Cod sursa (job #1799353) | Cod sursa (job #2331240) | Cod sursa (job #327718) | Cod sursa (job #2086064) | Cod sursa (job #668744)
Cod sursa(job #668744)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
char a[2000001], b[2000001];
int n, m, pi[2000001], p = 0, sp[2001];
void make_prefix() {
int i, k = 0;
for(i = 2; i <= n; ++i) {
while(k > 0 && a[k + 1] != a[i])
k = pi[k];
if(a[k + 1] == a[i])
++k;
pi[i] = k;
}
}
int main() {
int i, k = 0;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(a + 1, 2000001);
f.getline(b + 1, 2000001);
n = strlen(a + 1); m = strlen(b + 1);
make_prefix();
for(i = 1; i <= m; ++i) {
while(k > 0 && a[k + 1] != b[i])
k = pi[k];
if(a[k + 1] == b[i])
++k;
if(k == n) {
k = pi[k];
if(p < 1000) sp[++p] = (i - n);
}
}
g << p << '\n';
for(i = 1; i <= min(p, 1000); ++i)
g << sp[i] << ' ';
g.close();
return 0;
}