Cod sursa(job #3362380)

Utilizator JenJenCristache Ion JenJen Data 7 august 2026 22:01:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;

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

string a, b;
int z[2000005];

int main()
{
    in >> a >> b;

    string rez;
    rez = a + '#' + b;

    int n = rez.size();

    z[ 0 ] = n;
    int leftt = 0;
    int rightt = 0;

    for (int i = 1; i < n; i++)
    {
        if (i > rightt)
        {
            leftt = rightt = i;
            while (rez[rightt] == rez[rightt - leftt] && rightt < n)
            {
                rightt++;
            }

            z[leftt] = rightt - leftt;
            rightt--;

        } else
        {
            if (z[i - leftt] < rightt - i + 1)
            {
                z[i] = z[i - leftt];
            } else
            {
                leftt = i;
                while (rez[rightt] == rez[rightt - leftt] && rightt < n)
                {
                    rightt++;
                }

                z[leftt] = rightt - leftt;
                rightt--;
            }
        }
    }

    long long nr = 0;
    for (int i = a.size() + 1; i < n; i++)
    {
        if (z[i] == a.size())
        {
            nr++;
        }
    }

    out << nr << "\n";
    for (int i = a.size() + 1; i < n; i++)
    {
        if (z[i] == a.size())
        {
            out << i - a.size() - 1 << " ";
        }
    }
    return 0;
}