Pagini recente » Cod sursa (job #2464816) | Cod sursa (job #2589583) | Cod sursa (job #1461094) | Cod sursa (job #132726) | Cod sursa (job #2480835)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[NMAX],b[NMAX];
int n,m,l[NMAX],out[1005];
void prefix()
{
int j=0;
for (int i=2;i<=n;i++)
{
while(j!=0&&a[i]!=a[j+1])
j=l[j];
if (a[i]==a[j+1])
j++;
l[i]=j;
}
}
int main()
{
fin.getline(a+1,NMAX);
fin.getline(b+1,NMAX);
n=strlen(a+1);
m=strlen(b+1);
prefix();
int j=0,nr=0;
for (int i=1;i<=m;i++)
{
while(j!=0&&b[i]!=a[j+1])
j=l[j];
if (b[i]==a[j+1])
{
j++;
if (j==n)
{
if (nr<=1000)
out[nr]=i-n;
nr++;
}
}
}
fout<<nr<<'\n';
for (int i=0;i<nr&&i<1000;i++)
fout<<out[i]<<' ';
return 0;
}