Cod sursa(job #923553)
#include <fstream>
#include <cstring>
using namespace std;
static const int MAXN = 2000001, MAXA = 1000;
char T[MAXN], P[MAXN], PI[MAXN];
int A[MAXA], kt;
void pre() {
int k = PI[0] = 0;
for(int i = 1; P[i]; i++) {
while(k > 0 && P[k] != P[i]) k = PI[k - 1];
if(P[k] == P[i]) k++;
PI[i] = k;
}
}
int main() {
int ans = 0, lP, lT, lastP;
ifstream f("strmatch.in");
f >> P >> T;
f.close();
lP = strlen(P);
lT = strlen(T);
lastP = lT - lP + 1;
int k = 0;
for(int i = 0; i < lastP; i++) {
while(k > 0 && P[k] != T[i]) k = PI[k - 1];
if(P[k] == T[i]) k++;
if(!P[k]) {
if(kt < 1000) A[kt++] = i;
ans++;
}
}
ofstream g("strmatch.out");
g << ans << endl;
for(int i = 0; i < kt; i++) {
g << A[i] << ' ';
}
g << endl;
g.close();
return 0;
}