Cod sursa(job #2641420)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 11 august 2020 13:08:05
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 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][100005];
int fr[260], lg[1000005];

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

void Suffix_Array () {
    lg[1] = 0;
    for (int i = 2; i <= sir.size(); ++ i ) {
        lg[ i ] = lg[ i / 2 ] + 1;
    }
    for (int i = 0; i < sir.size(); ++ i ) {
        fr[sir[ i ] - '0']++;
    }
    int cnt = 0;
    for (int i = 0; i < 260; ++ i ) {
        if (fr[ i ] != 0) {
            ++ cnt;
            fr[ i ] = cnt;
        }
    }

    for (int i = 0; i < sir.size(); ++ i ) {
        Suffix[ 0 ][ i ] = fr[ sir[ i ] - '0' ];
    }

    for (int i = 1; (1<<(i-1)) <= sir.size(); ++ i ) {
        for (int j = 0; j < sir.size(); ++ j ) {
            K[ j ] = {{Suffix[i-1][j], (j + (1<<(i-1)) < sir.size() ? Suffix[i-1][j+(1<<(i-1))] : 0) }, 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 = 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 <= B.size() - 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;
}