Pagini recente » Cod sursa (job #924907) | Cod sursa (job #343914) | Cod sursa (job #1054621) | Cod sursa (job #95216) | Cod sursa (job #629196)
Cod sursa(job #629196)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMax 2000003
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long urm[NMax], M,N,nr,pos[NMax];
char A[NMax],B[NMax];
long minim(long x, long y)
{
if(x<y)
return x;
return y;
}
void citire()
{
long i;
f>>A>>B;
M=strlen(A);
N=strlen(B);
for(i=M;i>0;--i)
A[i]=A[i-1];
for(i=N;i>0;--i)
B[i]=B[i-1];
f.close();
}
void prefixeaza()
{
long i,k=0;
urm[1]=0;
for(i=2;i<=M;i++)
{
while(k && A[k+1]!=A[i])
k=urm[k];
if(A[k+1]==A[i])
++k;
urm[i]=k;
}
}
void match()
{
long i,k=0;
prefixeaza();
for(i=1;i<=N;i++)
{
while(k && A[k+1]!=B[i])
k=urm[k];
if(A[k+1]==B[i])
k++;
if(k==M)
{
nr++;
if(nr<=1000)
pos[nr]=i-M;
k=urm[k];
}
}
g<<nr<<'\n';
for(i=1;i<=minim(nr,1000);i++)
g<<pos[i]<<' ';
g.close();
}
int main()
{
citire();
match();
return 0;
}