Pagini recente » Cod sursa (job #2337046) | Istoria paginii runda/sasasas/clasament | Cod sursa (job #1609673) | Cod sursa (job #1338034) | Cod sursa (job #188718)
Cod sursa(job #188718)
#include <stdio.h>
using namespace std;
#define min(a,b) ((a<b)?a:b)
#define max 2000005
int m, n;
char s1[max],s2[max];
int pi[max],pos[1024];
void make_prefix()
{
int i,q=0;
for(i=2,pi[1]=0;i<=m;++i){
while(q && s1[q+1]!=s1[i])
q=pi[q];
if(s1[q+1]==s1[i])
++q;
pi[i]=q;
}
}
int main()
{
int i,q=0,nr=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1,sizeof(s1),stdin);
fgets(s2,sizeof(s2),stdin);
for(;(s1[m]>='A' && s1[m]<='Z') || (s1[m]>='a' && s1[m]<='z') || (s1[m]>='0' && s1[m]<='9'); ++m);
for(;(s2[n]>='A' && s2[n]<='Z') || (s2[n]>='a' && s2[n]<='z') || (s2[n]>='0' && s2[n]<='9'); ++n);
for(i=m;i;--i)
s1[i]=s1[i-1];
s1[0]=' ';
for(i=n;i;--i)
s2[i]=s2[i-1];
s2[0]=' ';
make_prefix();
for(i=1;i<=n;++i){
while(q && s1[q+1]!=s2[i])
q=pi[q];
if(s1[q+1]==s2[i])
++q;
if(q==m){
q=pi[m];
++nr;
if(nr<=1000)
pos[nr]=i-m;
}
}
printf("%d\n",nr);
for(i=1;i<=min(nr,1000);++i)
printf("%d ",pos[i]);
printf("\n");
fcloseall();
return 0;
}