Pagini recente » Cod sursa (job #2891538) | Cod sursa (job #2697256) | Cod sursa (job #1838411) | Cod sursa (job #771803) | Cod sursa (job #1808851)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000010], B[2000010];
int q, prefix[2000010],LGa,LGb;
int n, poz[1024];
void make_prefix()
{
q=0;
int i;
for(i=2,prefix[1]=0; i<=LGa; i++)
{
while(q>0 && A[q+1]!=A[i])
q=prefix[q];
if(A[q+1]==A[i])
q++;
prefix[i]=q;
}
}
int main()
{
fin>>A>>B;
q=0;
LGa=strlen(A);
LGb=strlen(B);
for(int i=LGa;i>0;i--)A[i]=A[i-1];A[0]='#';
for(int i=LGb;i>0;i--)B[i]=B[i-1];B[0]='#';
make_prefix();
q=0;
n=0;
for(int i=1; i<=LGb; i++)
{
while(q>0 && A[q+1]!=B[i])
q=prefix[q];
if(A[q+1]==B[i])
q++;
if(q==LGa)
{
n++;
q=prefix[LGa];
if(n<=1000)
poz[n]=i-LGa;
}
}
fout<<n<<'\n';
int k=min(n,1000);
for(int i=1; i<=k; i++)
{
fout<<poz[i];
if(i!=n)
fout<<' ';
}
return 0;
}