Cod sursa(job #1228557)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 14 septembrie 2014 16:29:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
using namespace std;
#include <fstream>
#define Lgmax 2000002

int p[Lgmax], sol[Lgmax], nrSol = 0;
char a[Lgmax], b[Lgmax];

void read() ;
int preprocess(char*, int*) ;
void write() ;

int main()
{
    int i, k, m;
    read();
    m = preprocess(a, p);
    
    for(i = 1, k = 0; b[i] != '\0'; ++i)
    {
        while(k > 0 && b[i] != a[k + 1])
            k = p[k];
        if(b[i] == a[k + 1]) ++k;
        if(k == m) sol[++nrSol] = i - m;
    }
    
    write();
    return 0;
}

void read()
{
    ifstream fin("strmatch.in");
    fin.getline(a + 1, Lgmax);
    fin.getline(b + 1, Lgmax);
    fin.close();
}


int preprocess(char s[], int v[])
{
    int k, q;
    v[0] = v[1] = 0;
    
    for(q = 2, k = 0; s[q] != '\0'; ++q)
    {
        while(k > 0 && s[q] != s[k + 1]) k = v[k];
        if(s[q] == s[k + 1]) ++k;
        v[q] = k;
    }
    
    return q - 1;
}


void write()
{
    ofstream fout("strmatch.out");
    
    fout << nrSol << '\n';
    nrSol = min(nrSol, 1000);
    for(int i = 1; i <= nrSol; ++i)
        fout << sol[i] << ' ';
    fout << '\n';
    
    fout.close();
}