Pagini recente » Cod sursa (job #2771089) | Cod sursa (job #3127325) | Cod sursa (job #2840887) | Cod sursa (job #394061) | Cod sursa (job #1954031)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define Nmax 2000005
int n, m, Prfx[Nmax], Sol[1005], k;
char A[Nmax], B[Nmax];
void Prefix() {
int q = 0;
for(int i = 2; i <= n; ++i) {
while(q && A[q + 1] != A[i])
q = Prfx[q];
if(A[q + 1] == A[i])
++q;
Prfx[i] = q;
}
}
int main()
{
fin >> A + 1;
fin >> B + 1;
A[0] = B[0] = ' ';
n = strlen(A + 1);
m = strlen(B + 1);
Prefix();
int q = 0;
for(int i = 1; i <= m; ++i) {
while(q && A[q + 1] != B[i])
q = Prfx[q];
if(A[q + 1] == B[i])
++q;
if(q == n) {
q = Prfx[n];
++k;
if(k <= 1000)
Sol[k] = i - n;
}
}
fout << k << '\n';
for(int i = 1; i <= min(1000, k); ++i)
fout << Sol[i] << ' ';
return 0;
}