Pagini recente » Cod sursa (job #2500384) | Cod sursa (job #2405056) | Cod sursa (job #461866) | Cod sursa (job #1972993) | Cod sursa (job #651852)
Cod sursa(job #651852)
#include <cstdio>
#include <cstring>
#define PL 2000002
#define TL 2000002
#define vL 1001
int L[PL];
int v[vL];
char P[PL];
char T[TL];
int main()
{
int M,N;
freopen("strmatch.in","r",stdin);
fgets(P+1,PL,stdin);
fgets(T+1,TL,stdin);
M=strlen(P+1)-1;
N=strlen(T+1)-1;
for(int k=0,i=2;i<=M;++i)
{
for(;k&&P[i]==P[k+1];k=L[k]);
if(P[k+1]==P[i]) ++k;
L[i]=k;
}
for(int k=0,i=1;i<=N;++i)
{
for(;k&&P[k+1]!=T[i];k=L[k]);
if(P[k+1]==T[i]) ++k;
if(k==M)
{
++v[0];
if(v[0]<=1000) v[v[0]]=i-M;
}
}
freopen("strmatch.out","w",stdout);
printf("%d\n",v[0]);
for(int i=1;i<v[0]&&i<1000;++i)
printf("%d ",v[i]);
if(v[0]<1000) printf("%d\n",v[v[0]]);
else printf("%d\n",v[1000]);
return 0;
}