Pagini recente » Cod sursa (job #3190513) | Cod sursa (job #3289880) | Rating C. Stefan (Zalmodegikos) | Cod sursa (job #1343155) | Cod sursa (job #694938)
Cod sursa(job #694938)
// Potrivirea sirurilor - KMP
#include <cstdio>
#include <cstring>
#define LMAX 2000011
using namespace std;
char a[LMAX],b[LMAX];
int nr,poz[1001],pi[LMAX];
int main()
{
int i,lg,q;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",a,b);
lg=strlen(a);
for(i=1;a[i];i++)
{
while( q>0 && a[i]!=a[q])
q=pi[q-1];
if(a[i]==a[q])
q++;
pi[i]=q;
}
q=0;
for(i=0;b[i];i++)
{
while(q && a[q]!=b[i])
q=pi[q-1];
if(a[q]==b[i])
q++;
if(q==lg)
{
q=pi[lg-1];
nr++;
if(nr<=1000)
poz[nr]=i-lg+1;
}
}
printf("%d\n",nr);
for(i=1;i<=nr and i<=1000;i++)
printf("%d ",poz[i]);
printf("\n");
return 0;
}