Cod sursa(job #2304508)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 18 decembrie 2018 09:37:01
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

string A, B, C;
int patternSize, Z[4000005];

void CalculateZ()
{
    int st = 0, dr = 0;

    for(int i = 1; i < C.size(); i++)
        if(i > dr)
        {
            st = dr = i;

            while(dr < C.size() && C[dr] == C[dr - st])
                dr++;

            Z[i] = dr - st;
            dr--;
        }
        else
        {
            if(Z[i - st] < dr - i + 1)
                Z[i] = Z[i - st];
            else
            {
                st = i;

                while(dr < C.size() && C[dr] == C[dr - st])
                    dr++;

                Z[i] = dr - st;
                dr--;
            }
        }
}

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

    for(int i = 0; i < A.size(); i++)
        C += A[i];
    C += '0';
    for(int i = 0; i < B.size(); i++)
        C += B[i];

    patternSize = A.size(); A.clear(); B.clear();
    CalculateZ();

    int nsol = 0;
    vector <int> sol;
    for(int i = 0; i < C.size(); i++)
        if(Z[i] == patternSize)
        {
            nsol++;

            if(sol.size() < 1000)
                sol.push_back(i - patternSize - 1);
        }

    fout << nsol << '\n';
    for(auto it : sol)
        fout << it << ' ';

    return 0;
}