Cod sursa(job #1921400)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 10 martie 2017 12:33:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
/**
  *  Worg
  */
#include <string>
#include <vector>
#include <fstream>

using std::vector;
using std::string;

std::ifstream cin("strmatch.in");
std::ofstream cout("strmatch.out");

const int kMaxLen = 1 + 2000000;
const int kMaxPrint = 1000;

/*-------- Input data --------*/
string A, B;
/*-------- Z-Algorithm --------*/
string S;
int z[kMaxLen * 2];
/*-------- Solution --------*/
int appearances_count;
vector<int > solution;
/*-------- --------*/

void ReadInput() {
    cin >> A >> B;
    S = A + B;
}

void RunZAlgorithm(const string &S) {
    //  z[i] = lungimea celei mai lungi secvente care incepe pe pozitia i si care este in acelasi timp prefix al sirului
    int left = -1, right = -1;  //  marginile z-boxului
    int N = S.size();

    for(int i = 1; i < N; i++) {
        ///  Z-Box : [left, right]
        if(i > right) {  //  Nu ne putem baza pe Z-box
            if(S[0] != S[i]) {
                z[i] = 0;
            } else {
                left = i; right = i - 1;
                for(int j = 0; right + 1 < N && S[j] == S[right + 1]; j++) {
                    right ++;
                    z[i] ++;
                }
            }
        } else {  //  Suntem in Z-Box
            int prev = i - left;
            if(z[prev] < right - i + 1) {
                z[i] = z[prev];
            } else {
                z[i] = right - i + 1;
                left = i;
                for(prev = z[i]; right + 1 < N && S[right + 1] == S[prev]; prev++) {
                    right ++;
                    z[i] ++;
                }
            }
        }
    }
}

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

    for(int i = M; i < N; i++) {
        if(z[i] >= M) {
            appearances_count ++;
            if(appearances_count <= kMaxPrint) {
                solution.push_back(i - M);
            }
        }
    }
}

void WriteOutput() {
    cout << appearances_count << '\n';
    for(auto index : solution) {
        cout << index << " ";
    }
}

int main() {
    ReadInput();
    RunZAlgorithm(S);
    GetSolution();
    WriteOutput();
    return 0;
}