Pagini recente » Cod sursa (job #2587576) | Cod sursa (job #1222990) | Cod sursa (job #2760229) | Cod sursa (job #1317005) | Cod sursa (job #518009)
Cod sursa(job #518009)
#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);
for(i=1;i<=nr;i++)
if(v[i]<=1000)
fprintf(g,"%d ",v[i]);
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}