Cod sursa(job #3258970)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 24 noiembrie 2024 16:11:01
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("a.in");
ofstream fout("a.out");

vector<int> ans;
string a, sir;
int target, N;
int *Z;

void Z_Algorithm() {
    int left, right;

    Z[0] = target;
    left = right = 0;

    for(int i = 1; i < N; i++)
        if(i > right) {
            left = right = i;

            while(right < N && sir[right - left] == sir[right])
                ++right;
            Z[i] = right - left;
            --right;
        } else {
            int k = i - left;
            if(Z[k] < right - i + 1)
                Z[i] = Z[k];
            else {
                left = i;
                while(right < N && sir[right - left] == sir[right])
                    ++right;
                Z[i] = right - left;
                --right;
            }
        }
}

int main()
{
    fin >> a >> sir;
    sir = a + "$" + sir;

    N = sir.size();
    target = a.size();

    Z = new int [N + 1];
    
    Z_Algorithm();

    int no = 0;
    for(int i = target; i < N; i++)
        if(Z[i] == target)
            if(ans.size() < 1000)
                ans.emplace_back(i - target - 1);
            else ++no;

    
    fout << ans.size() + no << '\n';
    for(auto x : ans)
        fout << x << ' ';
    fout << '\n';
    return 0;
}