Cod sursa(job #1811580)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 21 noiembrie 2016 12:44:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
/**
  *  Worg
  */
#include <string>
#include <vector>
#include <fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int MAX_LEN = (1 + 2000000) << 1;
const int MAX_SOL = 1000;

/*-------- Input data --------*/
string A, B;
/*-------- Z-Algorithm --------*/
string S;
int Z[MAX_LEN];
/*-------- Solution --------*/
int solutionCount;
vector< int > Solution;
/*-------- --------*/

void readInput() {
    fin >> A >> B;
}

void runZ_Algorithm() {
    int N = S.size();
    int L = -1, R = -1;

    for(int i = 1; i < N; i++) {
        if(i > R) {
            /* nu ne putem baza pe vreun Z-Box anterior */
            if(S[0] == S[i]) {
                L = i;
                R = i - 1;

                for(int j = 0, k = i; k < N && S[j] == S[k]; j++, k++) {
                    Z[i] ++;
                    R ++;
                }
            } else {
                Z[i] = 0;
            }
        } else {
            /* ne bazam pe Z-Boxul in care suntem */
            int before = i - L;
            if(Z[before] < R - i + 1) {
                Z[i] = Z[before];
            } else {
                Z[i] = R - i + 1;
                L = i;
                for(int before = Z[i]; R + 1 < N && S[R + 1] == S[before]; before++, R++) {
                    Z[i] ++;
                }
            }
        }
    }
}

void getSolution() {
    int N = S.size();
    int M = A.size();

    for(int i = M; i < N; i++) {
        if(Z[i] >= M) {
            solutionCount ++;
            if(solutionCount <= MAX_SOL) {
                Solution.push_back(i - M);
            }
        }
    }
}

void writeOutput() {
    fout << solutionCount << '\n';
    for(int i : Solution) {
        fout << i << " ";
    }
}

int main() {
    readInput();
    S = A + B;
    runZ_Algorithm();
    getSolution();
    writeOutput();
    return 0;
}