Pagini recente » Cod sursa (job #2395256) | Cod sursa (job #2395281) | Cod sursa (job #2395410) | Cod sursa (job #2394334) | Cod sursa (job #263927)
Cod sursa(job #263927)
#include<stdio.h>
#include<string.h>
#define infile "strmatch.in"
#define outfile "strmatch.out"
#define lmax (2*1000*1000+10)
#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;
int minim(int a, int b)
{
if(a<b) return a; return b;
}
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
if(++nr<nrmax) s[nr]=i-k; //salvam pozitia de inceput
}
//afisem
printf("%d\n",nr); //numarul de aparitii
for(i=1;i<=minim(nr,nrmax-1);printf("%d ",s[i++])); //pozitiile de start (doar pt primele NRMAX potriviri)
fclose(stdin);
fclose(stdout);
return 0;
}