Cod sursa(job #3362381)

Utilizator JenJenCristache Ion JenJen Data 7 august 2026 22:05:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 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 (rightt < n && rez[rightt] == rez[rightt - leftt])
            {
                rightt++;
            }

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

        } else
        {
            if (z[i - leftt] < rightt - i + 1)
            {
                z[i] = z[i - leftt];
            } else
            {
                leftt = i;
                while (rightt < n && rez[rightt] == rez[rightt - leftt])
                {
                    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";

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

    return 0;
}