Pagini recente » katyusha | Statistici Holom Adrian (holy) | Cod sursa (job #3226540) | Parantezare | Cod sursa (job #1648645)
#include <iostream>
#include <fstream>
#include <cstring>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char x[Nmax],y[Nmax];
int pi[Nmax];
int nrrez, rez[1001];
int main()
{
// citire
fin>>x+1>>y+1;
x[0]=y[0]=' ';
int n=strlen(x);
int m=strlen(y);
int k=0,i;
pi[1]=0;
// parcurgem x
for(i=2;i<=n;i++)
{
// cautam pozitia optima in prefix unde putem adauga noul element
while(k&&x[k+1]!=x[i])k=pi[k];
// daca gasim pozitia marim k (adaugam noul element la vechiul prefix)
if(x[k+1]==x[i])k++;
// actualizam pozitia in care se termina prefixul care este si sufix pentru sirul x[i]
pi[i]=k;
}
k=0;
// parcurgem y
for(i=1;i<=m;i++)
{
// cautam pozitia optima in prefix unde putem adauga noul element
while(k&&x[k+1]!=y[i])k=pi[k];
// daca gasim pozitia marim k (adaugam noul element la vechiul prefix)
if(x[k+1]==y[i])k++;
// daca lungimea prefixului coincide cu cea a sirului x atunci am gasit o potrivire
if(k==n-1)
{
// marim numarul de rezultate
nrrez++;
if(nrrez<=1000)
// adaugam noua pozitie
rez[nrrez]=i-n+1;
}
}
fout<<nrrez<<'\n';
for(i=1;i<=min(nrrez,1000);i++)
fout<<rez[i]<<' ';
return 0;
}