Pagini recente » Cod sursa (job #2062171) | Cod sursa (job #2062180) | Cod sursa (job #2062173) | Cod sursa (job #2062172) | Cod sursa (job #1227715)
#include <fstream>
#include <cstring>
#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 (i > R) {
Z[i] = 1;
while (i + Z[i] - 1 <= n && A[i + Z[i] - 1] == A[Z[i]])
++Z[i];
--Z[i];
L = i;
R = i + Z[i] - 1;
}
else {
int ii = i - L + 1;
if (Z[ii] < R - i + 1)
Z[i] = Z[ii];
else {
Z[i] = R - i + 1;
while (i + Z[i] - 1 <= n && A[i + Z[i] - 1] == A[Z[i]])
++Z[i];
--Z[i];
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;
if (sol == 1000)
break;
}
g << sol << "\n";
for (int i = 1; i <= sol; ++i)
g << Sol[i] << " ";
return 0;
}