Cod sursa(job #3333018)

Utilizator Radu_Tanasebitlevel Radu_Tanase Data 10 ianuarie 2026 15:09:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

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

#define MAX 2000001

string a, b;
int n, m, rez, lung_prefix_sufix[MAX], sol[MAX];

void constr_l_p_s()
{
    int i = 1, lung_prefix = 0;

    while(i < n)
    {
        if(a[i]==a[lung_prefix])
        {
            lung_prefix++;
            lung_prefix_sufix[i++] = lung_prefix;
        }
        else
        {
            if(lung_prefix)
                lung_prefix = lung_prefix_sufix[lung_prefix - 1];
            else
                lung_prefix_sufix[i++] = 0;
        }
    }
}

void cautare()
{
    int i = 0, lung_prefix = 0;
    while(i < m)
    {
        if(b[i] == a[lung_prefix])
        {
            i++;
            lung_prefix++;
            if(lung_prefix == n)
            {
                sol[++rez] = i - lung_prefix;
                lung_prefix = lung_prefix_sufix[lung_prefix - 1];
            }
        }
        else
        {
            if(lung_prefix)
                lung_prefix = lung_prefix_sufix[lung_prefix - 1];
            else
                i++;
        }
    }

    fout << rez << '\n';

    if(rez > 1000)
        rez = 1000;
    for(int i = 1; i <= rez; i++)
        fout << sol[i] << " ";
}

int main()
{
    fin >> a;
    fin.get();
    fin >> b;
    n=a.size();
    m=b.size();
    constr_l_p_s();
    cautare();
}