Pagini recente » Cod sursa (job #3132968) | Cod sursa (job #118924) | Cod sursa (job #1776433) | Cod sursa (job #1719124) | Cod sursa (job #172029)
Cod sursa(job #172029)
#include<stdio.h>
#include<string.h>
#define N 200000
char a[N],b[N];
int n,m,pi[N],nr,poz[N];
void prefix()
{
int i,k;
pi[1]=0;
k=0;
for(i=2;i<=n;i++)
{
while(k>0&&a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[k])
k++;
pi[i]=k;
}
}
void kmp()
{
int i,q;
q=0;
for(i=1;i<=m;i++)
{
while(q>0&&a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
q++;
if(q==n)
poz[++nr]=i-n;
}
}
void afis()
{
int i;
printf("%d\n",nr);
for(i=1;i<=nr;i++)
printf("%d ",poz[i]);
}
void solve()
{
int i;
scanf("%s\n",&a);
n=strlen(a);
for(i=n;i>=1;i--)
a[i]=a[i-1];
scanf("%s",&b);
m=strlen(b);
for(i=m;i>=1;i--)
b[i]=b[i-1];
prefix();
kmp();
afis();
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
solve();
return 0;
}