Pagini recente » Cod sursa (job #2344747) | Cod sursa (job #115207) | Cod sursa (job #1894293) | Cod sursa (job #1789415) | Cod sursa (job #2056333)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMax 2000005
int M, N,i,n ;
char A[NMax], B[NMax];
int q,pi[NMax], pos[2000004];
void prefix()
{
int i, q = 0;
for (i = 2, pi[1] = 0; i <= M; ++i)
{
while (q && A[q+1] != A[i]) q = pi[q];
if (A[q+1] == A[i]) ++q;
pi[i] = q;
}
}
int main()
{
fin.getline(A,NMax);
fin.getline(B,NMax);
M=strlen(A);
N=strlen(B);
for (i = M; i; --i) A[i] = A[i-1]; A[0] = ' ';
for (i = N; i; --i) B[i] = B[i-1]; B[0] = ' ';
prefix();
for (i = 1; i <= N; ++i)
{
while (q && A[q+1] != B[i]) q = pi[q];
if (A[q+1] == B[i]) ++q;
if (q == M)
{ q = pi[M];
++n;
pos[n] = i-M;
}
}
fout<<n<<'\n';
for (i = 1; i <= n;++i) fout<<pos[i]<<' ';
fout<<'\n';
return 0;
}