Cod sursa(job #2762398)

Utilizator dragutamihai1234Draguta Mihai dragutamihai1234 Data 6 iulie 2021 20:27:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

string pattern,sir;
int lung,lungime;
int z[4000005];

vector<int>sol;

void Z_algorithm()
{
    int L=0,R=0;

    int n=lung;

    for (int i = 1; i < n; i++)
    {
        if (i > R)
        {
            L = R = i;
            while (R < n && pattern[R-L] == pattern[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 && pattern[R-L] == pattern[R]) R++;
                z[i] = R-L;
                R--;
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        if( i>=lungime&&z[i]>=lungime )
        {
            sol.push_back(i-lungime);
        }
    }
}

int main()
{
    f>>pattern;
    f>>sir;

    lungime=pattern.size();
    pattern+=sir;

    lung=pattern.size();

    Z_algorithm();

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

    for(int i=0; i<sol.size()&&i<1000; i++) g<<sol[i]<<' ';

    return 0;
}