Pagini recente » Cod sursa (job #1337229) | Cod sursa (job #2070620) | Cod sursa (job #1343749) | Cod sursa (job #3250984) | Cod sursa (job #1808843)
#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)
{
q=prefix[LGa];
if(n<1000)
poz[++n]=i-LGa;
}
}
fout<<n<<'\n';
for(int i=1; i<=n; i++)
{
fout<<poz[i];
if(i!=n)
fout<<' ';
}
return 0;
}