Pagini recente » Cod sursa (job #907841) | Cod sursa (job #171792) | Statistici Stefana Arina Tabusca (StefanaArina) | Cod sursa (job #411529) | Cod sursa (job #1330769)
#include <cstdio>
#include <cstring>
#define DMAX 2000010
using namespace std;
char a[DMAX], b[DMAX];
int mat[2][DMAX], lg1, lg2;
int n, m;
void citire();
void rez();
void afisare(int);
int main()
{
citire();
rez();
return 0;
}
void citire()
{
FILE*fin=fopen ("strmatch.in", "r");
fscanf(fin, "%s", a);
fscanf(fin, "%s", b);
n=strlen (a); m=strlen (b);
fclose(fin);
return;
}
void rez()
{
int poz=0, lcrt=1, lprec=0, i;
//initializez prima linie a matricei
for (i=0; i<m; ++i)
if (a[0]==b[i])
mat[0][++lg1]=i;
poz=1;
while (poz<n)
{
//verific pentru toate pozitiile curente
for (i=1; i<=lg1; ++i)
if (a[poz]==b[mat[lprec][i]+1])
mat[lcrt][++lg2]=mat[lprec][i]+1;
lg1=lg2; lg2=0;
lcrt=1-lcrt; lprec=1-lprec;
++poz;
}
//la final mi-au ramas doar pozitiile bune
afisare (lprec);
return;
}
void afisare(int lin)
{
int i;
FILE*fout=fopen ("strmatch.out", "w");
if (lg1>1000) lg1=1000;
fprintf(fout, "%d\n", lg1);
for (i=1; i<=lg1; ++i)
fprintf(fout, "%d ", mat[lin][i]-n+1);
fprintf(fout, "\n");
fclose(fout);
return;
}