Cod sursa(job #2641432)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 11 august 2020 13:22:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

string A, B, sir;

int Suffix[30][200005];
int lg[200005];

pair <pair <int, int>, int> K[200005];

void Suffix_Array () {
    lg[1] = 0;
    for (int i = 2; i <= sir.size(); ++ i ) {
        lg[ i ] = lg[ i / 2 ] + 1;
    }

    for (int j = 0; j < sir.size(); ++ j ) {
        K[ j ] = {{sir[j], 0}, j};
    }
    sort(K, K+sir.size());
    int cnt = 1;
    Suffix[0][K[0].second] = 1;
    for (int j = 1; j < sir.size(); ++ j ) {
        if (K[j].first != K[j-1].first) ++ cnt;

        Suffix[0][K[j].second] = cnt;
    }

    for (int i = 1; (1<<(i-1)) <= sir.size(); ++ i ) {
        for (int j = 0; j < sir.size(); ++ j ) {
            K[ j ] = {{Suffix[i-1][j], Suffix[i-1][j+(1<<(i-1))]}, j};
        }

        sort(K, K+sir.size());

        int cnt = 1;
        Suffix[i][K[0].second] = 1;
        for (int j = 1; j < sir.size(); ++ j ) {
            if (K[j].first != K[j-1].first) ++ cnt;

            Suffix[i][K[j].second] = cnt;
        }
    }
}

int LCP (int i, int j) {
    int ans = 0, M = (int)sir.size() - max(i, j);

    for (int p = lg[M]; p >= 0; -- p ) {
        if (Suffix[p][i] == Suffix[p][j]) {
            ans += (1<<p);
            i += (1<<p);
            j += (1<<p);
        }
    }

    return ans;
}

int main()
{
    f >> A >> B;

    sir = B + A;

    Suffix_Array();

    vector <int> sol;

    for (int i = 0; i <= (int)B.size() - (int)A.size(); ++ i ) {
        int val = LCP(i, B.size());

        if (val >= A.size()) {
            sol.push_back(i);
        }
    }

    g << sol.size() << '\n';

    for (int i = 0; i < min(1000, (int)sol.size()); ++ i ) {
        g << sol[ i ] << " ";
    }
    return 0;
}