Pagini recente » Cod sursa (job #1245187) | Cod sursa (job #1428981) | Cod sursa (job #304632) | Cod sursa (job #2465039) | Cod sursa (job #2335628)
#include <cstring>
#include <cstdio>
using namespace std;
char a[2000005];
int p[2000005];
char b[2000005];
int m;
void constrPrefix()
{
m=strlen(a+1);
p[1]=0;
int i=0;
for(int j=2; j<=m; j++)
{
while(i>0 && a[i+1]!=a[j])
{
i=p[i];
}
if(a[i+1]==a[j])
++i;
p[j]=i;
}
}
int afis[1005], nr;
void stringMatching()
{
int k=0;
int n=strlen(b+1);
for(int i=1; i<=n;i++)
{
while(k && b[i] != a[k+1])
k = p[k];
if(b[i]==a[k+1])
k++;
if(k==m)
{
nr++;
if(nr<=1000)
afis[nr]=i-m;
k=p[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n",a+1);
scanf("%s",b+1);
constrPrefix();
stringMatching();
printf("%d\n",nr);
int aa=nr;
if(nr>1000)
aa=1000;
for(int i=1; i<=aa; i++)
printf("%d ",afis[i]);
return 0;
}