Pagini recente » Cod sursa (job #2623399) | Cod sursa (job #919037) | Cod sursa (job #2061328) | Borderou de evaluare (job #366978) | Cod sursa (job #2064559)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int const lenmax = (int) 2e6;
string x, y;
int pre[lenmax], sol[1005];
void buildPre() {
int i = 0, j = 1;
while(j < x.size()) {
if(x[i] == x[j]) {
pre[j] = pre[j - 1] + 1;
++ j;
++ i;
} else {
if(i == 0) {
pre[j] = 0;
++ j;
} else {
i = pre[i - 1];
}
}
}
}
int main() {
in >> x >> y;
buildPre();
int nsol = 0;
int i = 0, j = 0;
while(j < y.size()) {
while(i < x.size() && x[i] == y[j]) {
++ i, ++ j;
}
if(i == 0) {
++ j;
} else {
if(i == x.size()) {
if(nsol < 1000)
sol[nsol] = j - x.size();
nsol++;
}
i = pre[i - 1];
}
}
out << nsol << '\n';
for(int i = 0; i < min(nsol, 1000); i++)
out << sol[i] <<" ";
return 0;
}