Cod sursa(job #3004532)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 16 martie 2023 13:17:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 2e6 + 2;
int N;
int z[nmax];
string concat,text,pattern;
vector<int> rasp;

inline void create_Z_array()
{
    z[0] = 0;
    int right = 0, left = 0;
    for(int i=1; i < N; i++)
    {
        if(i > right)
        {
            right = left = i;
            while(right < N && concat[right] == concat[right - left])
                right ++;
            z[i] = right - left;
            right --;
        }
        else if(z[i - left] < right - i + 1)
        {
            z[i] = z[i - left];
        }
        else
        {
            left = i;
            while(right < N && concat[right] == concat[right - left])
                right ++;
            z[i] = right - left;
            right --;
        }
    }
}

int main()
{
    fin>>pattern>>text;
    concat = pattern + '$' + text;
    N = concat.length();
    create_Z_array();
    for(int i=1; i < N; i++)
    {
        if(z[i] == pattern.length())
            rasp.push_back(i - pattern.length() - 1);
    }
    int n = rasp.size();
    fout<<n<<"\n";
    for(int i=0; i < min(n,1000); i++)
    {
        fout<<rasp[i]<<" ";
    }
    return 0;
}