Pagini recente » Cod sursa (job #2715923) | Cod sursa (job #1939787) | Cod sursa (job #2612581) | Cod sursa (job #3236236) | Cod sursa (job #2336677)
#include <cstdio>
#include <cstring>
using namespace std;
char s[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(s+1);
int k=0;
for(int i=1;i<=n;i++)
{
while(k && s[i]!=a[k+1])
k=p[k];
if(s[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",s+1);
formPrefix();
stringMatching();
int aa=nr;
if(aa>=1000)
aa=1000;
printf("%d\n",aa);
for(int i=1; i<=aa; i++)
{
printf("%d ",afis[i]);
}
return 0;
}