Pagini recente » Cod sursa (job #496516) | Cod sursa (job #531983) | Cod sursa (job #618081) | Cod sursa (job #2778072) | Cod sursa (job #629189)
Cod sursa(job #629189)
#include <iostream>
#include <fstream>
#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];
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++;
pos[nr]=i-M;
}
}
g<<nr<<'\n';
for(i=1;i<=nr;i++)
g<<pos[i]<<' ';
g.close();
}
int main()
{
citire();
match();
return 0;
}