Pagini recente » Cod sursa (job #1282761) | Cod sursa (job #1390802) | Cod sursa (job #2886147) | Cod sursa (job #820060) | Cod sursa (job #2910317)
#include <iostream>
#include <fstream>
#include <cstring>
#define DIM 2000000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
char A[DIM+2], B[DIM+2];
int P[DIM+2], sol[1001];
int a, b, i, L, nr;
int main ()
{
fin>>A+1;
fin>>B+1;
a = strlen(A+1);
b = strlen(B+1);
L = 0;
P[1] = 0;
for (int i=2; i<=a; 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 (i=1; i<=b; i++)
{
while (L != 0 && B[i]!=A[L+1])
L = P[L];
if (B[i] == A[L+1])
{
L++;
}
if (L == a)
{
nr++;
if (nr<=1000)
{
sol[nr] = i-a;
}
L = P[L];
}
}
fout<<nr<<"\n";
for (int i=1; i<=min(1000, nr); i++)
{
fout<<sol[i]<<" ";
}
return 0;
}