Pagini recente » Cod sursa (job #958328) | Cod sursa (job #1521594) | Cod sursa (job #1282858) | Cod sursa (job #1599439) | Cod sursa (job #480835)
Cod sursa(job #480835)
#include<algorithm>
using namespace std;
#define DIM 2000005
#define DIM2 1005
char a[DIM],b[DIM];
int n,m,s[DIM],sol[DIM2],vf;
void read ()
{
fgets (a,sizeof(a),stdin);
fgets (b,sizeof(b),stdin);
for(n=0;('0'<=a[n] && a[n]<='9') || ('A'<=a[n] && a[n]<='Z') || ('a'<=a[n] && a[n]<='z');++n);
for(m=0;('0'<=b[m] && b[m]<='9') || ('A'<=b[m] && b[m]<='Z') || ('a'<=b[m] && b[m]<='z');++m);
}
void kmp ()
{
int i,q=0;
for(i=0;i<m;++i)
{
while(q && a[q+1]!=b[i])
q=s[q];
if(a[q+1]==b[i])
++q;
s[i]=q;
}
for(i=0;i<m;++i)
{
if(s[i]==n-1)
sol[++vf]=i-n+1;
if(vf==1000)
return ;
}
}
void show ()
{
int i;
printf("%d\n",vf);
for(i=1;i<=vf;++i)
printf("%d ",sol[i]);
}
int main ()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read ();
kmp ();
show ();
return 0;
}