Pagini recente » Cod sursa (job #1458024) | Cod sursa (job #89409) | Cod sursa (job #1330079) | Cod sursa (job #1155033) | Cod sursa (job #2335626)
#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);
for(int i=1; i<=nr; i++)
printf("%d ",afis[i]);
return 0;
}