Cod sursa(job #3247582)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 8 octombrie 2024 15:29:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "strmatch";

std :: ifstream f (FILENAME + ".in");

std :: ofstream g (FILENAME + ".out");

const int NMAX = 2e6 + 5;

int cnt;

int z[2 * NMAX];

std :: string a;

std :: string b;

std :: string s;

void _z(const std :: string & s)
{
    int l = 0;

    int r = 0;

    for(int i = 1; i < s.size(); i ++)
    {
        if(i < r)
        {
            z[i] = std :: min(r - i, z[i - l]);
        }

        while(s[z[i]] == s[i + z[i]])
        {
            z[i] ++;
        }

        if(r < i + z[i])
        {
            r = i + z[i];

            l = i;
        }
    }
}

int main()
{

    f >> a >> b;

    s = a + "*" + b;

    _z(s);

    for(int i = 0; i < s.size(); i ++)
    {
        if(z[i] == a.size())
        {
            cnt ++;
        }
    }

    g << cnt << '\n';

    cnt = 0;

    for(int i = 0; i < s.size(); i ++)
    {
        if(z[i] == a.size())
        {
            cnt ++;

            g << i - a.size() - 1 << " ";

            if(cnt == 1000)
            {
                return 0;
            }
        }
    }

    return 0;
}