Pagini recente » Cod sursa (job #2062178) | Borderou de evaluare (job #3101261) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1226784)
#include <fstream>
#include <cstring>
#define DIM 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[DIM], B[DIM], C[DIM];
int Pi[DIM];
int sol, Sol[DIM];
int main() {
fin >> B;
fin >> A;
int n = strlen(A);
int m = strlen(B);
strcpy(C, B);
strcpy(B + 1, C);
strcpy(C, A);
strcpy(A + 1, C);
for (int i = 2; i <= m; ++i) {
int q = Pi[i - 1];
while (q && B[i] != B[q + 1])
q = Pi[q];
if (B[i] == B[q + 1])
Pi[i] = q + 1;
}
int q = 0;
for (int i = 1; i <= n; ++i) {
while (q && A[i] != B[q + 1])
q = Pi[q];
if (A[i] == B[q + 1])
q++;
if (q == m) {
++sol;
Sol[sol] = i - m;
q = Pi[q];
}
}
fout << sol << "\n";
for (int i = 1; i <= sol && i <= 1000; ++i)
fout << Sol[i] << " ";
return 0;
}