Pagini recente » Cod sursa (job #491895) | Cod sursa (job #577395) | Cod sursa (job #1564693) | Cod sursa (job #2102782) | Cod sursa (job #518015)
Cod sursa(job #518015)
#include<stdio.h>
#include<string.h>
using namespace std;
#define Max 2000000
int urm[Max],nr,v[Max];
char T[Max],P[Max];
int n,m;
void urmatorul (char *p)
{
int k=-1, x;
urm[0]=0;
for(x=1;x<m;x++)
{
while(k>0 && P[k+1]!=P[x])
k=urm[k];
if(P[k+1]==P[x])
k++;
urm[x]=k;
}
}
int main()
{
FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");
int i,x=-1;
fscanf(f,"%s", P); fscanf(f,"%s", T);
n=strlen(T); m=strlen(P);
urmatorul(P);
for(i=0;i<n;i++)
{
while(x>0 && P[x+1]!=T[i])
x=urm[x];
if(P[x+1]==T[i])
x++; //s-au potrivit
if(x==m-1)
{
nr++;
v[nr]=i-m+1;
//printf("Am gasit subsirul in pozitia %d\n",i-m+1);
x=urm[x];
}
}
fprintf(g,"%d\n",nr);
if(nr>1001)
nr=1001;
for(i=1;i<=nr;i++)
fprintf(g,"%d ",v[i]);
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}