Pagini recente » Cod sursa (job #1129175) | Cod sursa (job #1974520) | Cod sursa (job #2005654) | Cod sursa (job #2952348) | Cod sursa (job #616084)
Cod sursa(job #616084)
#include<stdio.h>
#include<string.h>
using namespace std;
int pi[2000005],pos[2000005],n,m,j;
char a[2000005],b[2000005];
void calcul_prefix()
{
int k=0,i;
for(i=2;i<=n;i++)
{
while(k>0&&a[i]!=a[k+1])
k=pi[k];
if(a[i]==a[k+1])
++k;
pi[i]=k;
}
}
void potrivire()
{
int k=0,i;
for(i=1;i<=m;i++)
{
while(k>0&&b[i]!=a[k+1])
k=pi[k];
if(b[i]==a[k+1])
++k;
if(k==n)
{
k=pi[n];
j++;
if(j<=1000)
{
pos[j]=i-n;
}
}
}
}
int main()
{
freopen ("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,sizeof(a),stdin);
fgets(b,sizeof(b),stdin);
while(a[n]<='Z'&&a[n]>='A'||a[n]<='z'&&a[n]>='a'||a[n]<='9'&&a[n]>='0')
++n;
while(b[m]<='Z'&&b[m]>='A'||b[m]<='z'&&b[m]>='a'||b[m]<='9'&&b[m]>='0')
++m;
int i;
for(i=n;i>0;i--)
a[i]=a[i-1];
a[0]=' ';
for(i=m;i>0;i--)
b[i]=b[i-1];
b[0]=' ';
calcul_prefix();
potrivire();
printf("%d\n",j);
if(j>1000)
j=1000;
for(i=1;i<=j;i++)
printf("%d ",pos[i]);
printf("\n");
return 0;
}