Pagini recente » Cod sursa (job #1357430) | Cod sursa (job #2575915) | Cod sursa (job #1705571) | Cod sursa (job #710277) | Cod sursa (job #3142107)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int DIM = 2000010;
const int SOL_DIM = 1000;
char a[DIM], b[DIM], A[DIM], B[DIM];
int p[DIM];
int sol[SOL_DIM + 1], solCnt;
int main() {
fin >> A >> B;
strcpy(a + 1, A);
strcpy(b + 1, B);
int n = strlen(a + 1);
int m = strlen(b + 1);
p[1] = 0;
int l = 0;
for (int i = 2; i <= n; i++) {
while (l != 0 && a[i] != a[l + 1])
l = p[l];
if (a[i] == a[l + 1])
l++;
p[i] = l;
}
l = 0;
for (int i = 1; i <= m; i++) {
while (l != 0 && b[i] != a[l + 1])
l = p[l];
if (b[i] == a[l + 1])
l++;
if (l == n) {
solCnt++;
if (solCnt <= 1000)
sol[solCnt] = i - n + 1;
l = p[l];
}
}
fout << solCnt << '\n';
for (int i = 1; i <= min(solCnt, SOL_DIM); i++)
fout << sol[i] - 1 << ' ';
return 0;
}