Pagini recente » Cod sursa (job #2360930) | Cod sursa (job #809717) | Cod sursa (job #808868) | Cod sursa (job #1709819) | Cod sursa (job #2714289)
#include <fstream>
#include <cstring>
#define fq 2000002
#define num 1000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A,B;
int nr,lg,i;
int p[fq],sol[fq];
int main()
{
//input
fin>>A>>B;
//solution
for(i=1; i<A.size(); i++)
{
while(lg && A[lg]!=A[i])
lg=p[lg-1];
if(A[lg]==A[i])
lg++;
p[i]=lg;
}
lg=0;
for(i=0; i<B.size(); i++)
{
while(lg && A[lg]!=B[i])
lg=p[lg-1];
if(A[lg]==B[i])
lg++;
if(lg==A.size())
sol[++nr]=i+1-A.size(), lg=p[lg-1];
}
//output
fout<<nr<<'\n';
for(i=1; i<=min(nr,num); i++)
fout<<sol[i]<<' ';
fout<<'\n';
return 0;
}