Pagini recente » Cod sursa (job #2087171) | Cod sursa (job #1474294) | Cod sursa (job #1185304) | Cod sursa (job #1586336) | Cod sursa (job #263878)
Cod sursa(job #263878)
#include<stdio.h>
#include<string.h>
#define infile "strmatch.in"
#define outfile "strmatch.out"
#define lmax (2*1000*1000+1)
#define nrmax 1001
char a[lmax],b[lmax]; //cele doua siruri
int s[nrmax]; //aici salvam potrivirile:P
int urm[lmax]; //vectorul care spune pozitia urmatoare
int n,m; //lungimile celor doua siruri
int nr;
void urmatorul()
{
int i,k=-1;
for(i=1;i<n;i++)
{
while(k>0&&a[i]!=a[k+1]) k=urm[k]; //cat timp nu gasim un sir pe care sa il putem continua
if(a[i]==a[k+1]) k++; //daca pozitia urmatoare este corecta, o continuam
urm[i]=k; //salvam lungimea
}
}
int main()
{
int i,k=-1;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
fgets(a,lmax,stdin); n=strlen(a)-1; //citim sirul si ii aflam lungimea (stergem caracterul \n)
fgets(b,lmax,stdin); m=strlen(b); //citim sirul si ii aflam lungimea
urmatorul(); //construim vectorul urm[]
//facem cautarea
for(i=0;i<m;i++)
{
while(k>0&&a[k+1]!=b[i]) k=urm[k];
if(b[i]==a[k+1]) k++; //se potriveste, deci inaintam
if(k==n-1) //inseamna k am gasit o asemanare a lui a in b
{
nr++; //salvam k am mai gasit o data
if(nr<nrmax)s[nr]=i-k; //salvam pozitia de inceput
}
}
//afisem
printf("%d\n",nr); //numarul de aparitii
for(i=1;i<=nr&&i<nrmax;printf("%d ",s[i++])); //afisem pozitiile de start (doar pt primele NRMAX potriviri)
fclose(stdin);
fclose(stdout);
return 0;
}