Cod sursa(job #1386798)

Utilizator rogoz.bogdanRogoz Bogdan rogoz.bogdan Data 13 martie 2015 11:47:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <cstring>
#define MX 2000005
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[MX], B[MX];
int T[MX], d[MX], n, m, total;

void Tabel()
{
    int i,k;

    k = 0;
    T[1] = 0;   //T[i] < i

    for(i=2; i<=n; i++)
    {
        while(k>0 && A[k+1]!=A[i])  //cat timp pref nu este nul si literele nu coincid sar din k in T[k]
        {
            k = T[k];
        }

        if(A[k+1] == A[i]) k++; //daca literele coincid
        T[i] = k;
    }
}

int main()
{
    int i,k,alese=0;

    fin.getline(A+1, MX, '\n');
    fin.getline(B+1, MX, '\n');

    n = strlen(A+1);
    m = strlen(B+1);
    //fout<<lga<<' '<<lgb;

    Tabel();

    k = 0;
    for(i=1; i<=m; i++)
    {
        while(k>0 && A[k+1]!=B[i]) k = T[k];

        if(A[k+1] == B[i]) k++; //daca literele coincid
        d[i] = k;

        if(k == n) total++;
    }

    fout<<total<<'\n';

    for(i=1; i<=m; i++)
    {
        if(d[i] == n)   //adica intreg sirul A coincide cu sufixul lui B[i]
        {
            fout<<i-n<<' '; //nu apare +1 pt ca am inceput numaratoarea de la 1
            alese++;

            if(alese == 1000) break;
        }
    }

    fin.close(); fout.close();
    return 0;
}