Pagini recente » Cod sursa (job #1834303) | Cod sursa (job #2348261) | Cod sursa (job #2031452) | Cod sursa (job #445757) | Cod sursa (job #2336681)
#include <cstdio>
#include <cstring>
using namespace std;
char b[2000005];
int p[2000005];
char a[2000005];
int m;
void formPrefix(){
m=strlen(a+1);
int i=0;
p[1]=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 n, nr;
int afis[1005];
void stringMatching()
{
n=strlen(b+1);
int k=0;
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);
formPrefix();
stringMatching();
int aa=nr;
printf("%d\n",aa);
if(aa>=1000)
aa=1000;
for(int i=1; i<=aa; i++)
{
printf("%d ",afis[i]);
}
return 0;
}