Cod sursa(job #3287027)

Utilizator average_disappointmentManolache Sebastian average_disappointment Data 14 martie 2025 23:03:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
//asta cica se cheama z
//vreau sa aflu de cate ori apare un prefix intr un vector v
//fie z[i] = lungimea maxima pt care [0, z[i] - 1] == [i, i + z[i] - 1]
//si [l, r] un interval cu R maxim pentru care [0, r - l] == [l, r] == z[l], pentru ca cu determinarea astora o sa te ocupi
//daca i pentru care vreau sa calculez z[i] > r, atunci fa brut si ia l = i
//cealata situatie este i apartine [l, r]
//atunci, fie k = i - l lungimea intervalului [l, i] - 1;
//avem ca z[i] >= min(z[k], r - i + 1), pentru ca minimul este lungimea pt care stim sigur ca v[k...] == v[i...]
//exista doua situatii acum
//z[k] < r - i + 1, deci diferenta apare in intervalul [0, r - l], pe care l am verificat
//caz in care e clar ca nu mai am nimic de facut decat sa avansez cu i
//si z[k] >= r - i + 1, in care nu mai stiu nimic despre unde apare diferenta
//asa ca faci brut
//numai ca de data asta iei l = i, ca sa foloseti faptul ca stii ca v[k, r - l] == v[i, r]
//aaaaaaaaaaaaaaaaaaaaaaaaaaaaa

#include <fstream>
#include <vector>
#include <string>

using namespace std;

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

const int NMAX = 2e6;

int z[2 * NMAX + 2];

int main() {
    
    int n, m;
    string a, b, v;
    cin >> a >> b;

    v = a + '$' + b;
    n = v.size();
    m = a.size();

    int l = 0, r = 0; //nu le initalizezi cu 1, n pt ca ideea e ca l, r se calculeaza pe masura ce mergi cu i
    z[1] = n;

    for (int i = 1; i < n; i++) {

        if (i > r) {
            l = r = i;
            while (r < n && v[r - l] == v[r])
                r++;
            z[i] = r - l;
            r--;
        }
        else {
            int k = i - l;
            if (z[k] < r - i + 1)
                z[i] = z[k]; 
            else {
                l = i;
                while (r < n && v[r - l] == v[r])
                    r++;
                z[i] = r - l;
                r--;
            }
        }
    }

    vector<int> occurences;
    for (int i = 0; i < n; i++)
        if (z[i] == m)
            occurences.push_back(i - m - 1);

    cout << occurences.size() << '\n';
    int count = 0;
    for (auto o : occurences) {
        count++;
        if (count > 1000)
            break;          //whyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
        cout << o << ' ';
    }
}