Pagini recente » Cod sursa (job #87673) | Cod sursa (job #2775195) | Cod sursa (job #2549835) | Cod sursa (job #2376500) | Cod sursa (job #651857)
Cod sursa(job #651857)
#include <cstdio>
#include <cstring>
#define PL 2000005
#define TL 2000005
#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)
{
while(k&&P[k+1]!=P[i]) k=L[k];
if(P[k+1]==P[i]) ++k;
L[i]=k;
}
for(int k=0,i=1;i<=N;++i)
{
while(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]);
if(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;
}