Pagini recente » Cod sursa (job #2062174) | Cod sursa (job #2147984) | Monitorul de evaluare | Cod sursa (job #1227716) | Cod sursa (job #1227718)
#include <fstream>
#include <cstring>
#define minim(a,b) (a>b ? b : a)
#define DIM 4000050
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[DIM], B[DIM];
int Z[DIM], Sol[DIM>>1];
int sol;
int main() {
f >> A;
f >> B;
int m = strlen(A);
strcat(A, B);
strcpy(B, A);
strcpy(A + 1, B);
int L = 0, R = 0;
int n = strlen(A + 1);
for (int i = 2; i <= n; ++i) {
if (R >= i)
Z[i] = minim(Z[i - L + 1], R - i + 1);
for (; i + Z[i] <= n && A[i + Z[i]] == A[1 + Z[i]]; ++Z[i]);
if (R < i + Z[i] - 1) {
R = i + Z[i] - 1;
L = i;
}
}
for (int i = m+1; i <= n; ++i)
if (Z[i] >= m) {
++sol;
Sol[sol] = i - m - 1;
}
g << sol << "\n";
for (int i = 1; i <= sol && i <= 1000; ++i)
g << Sol[i] << " ";
return 0;
}