Pagini recente » Cod sursa (job #2841688) | Cod sursa (job #566201) | Cod sursa (job #2301699) | Cod sursa (job #438915) | Cod sursa (job #1918080)
#include<cstdio>
#include<cstring>
using namespace std;
FILE *g=fopen("strmatch.out","w");
char P[2000002],T[2000002];
int pi[2000002];
int a[1001];
int n,m;
void prefix()
{
// int n,m;
n=strlen(T);
m=strlen(P);
pi[0]=0;
int k,i;
k=0;
for(i=1;i<=m-1;i++)
{
while(k>0 && P[i]!=P[k])
k=pi[k-1];
if(P[k]==P[i])
k=k+1;
pi[i]=k;
}
}
int main ()
{
FILE *f=fopen("strmatch.in","r");
fgets(P,2000000002,f);
P[strlen(P)-1]=NULL;
fgets(T,2000000002,f);
T[strlen(T)-1]=NULL;
// int n,m;
n=strlen(T);
m=strlen(P);
prefix();
/* for(int i=0;i<m;i++)
fprintf(g,"%d ",pi[i]);
fprintf(g,"\n");*/
int k,nr=0;
k=0;
for(int i=1;i<=n-1;i++)
{
while(k>0 && T[i]!=P[k])
k=pi[k-1];
if(P[k]==T[i])
k=k+1;
if(k==m)
{
nr++;
a[nr]=i-m+1;
k=pi[k-1];
}
}
fprintf(g,"%d\n",nr);
for(int i=1;i<=nr && i<=1001;i++)
fprintf(g,"%d ",a[i]);
fclose(f);
fclose(g);
return 0;
}