Pagini recente » Cod sursa (job #1293544) | Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/horeaoros | Cod sursa (job #668740)
Cod sursa(job #668740)
#include <fstream>
#include <cstring>
using namespace std;
char a[2000001], b[2000001];
int n, m, pi[2000001], p = 0, sp[2000001];
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 <= p; ++i)
g << sp[i] << ' ';
g.close();
return 0;
}