Cod sursa(job #3321055)

Utilizator Luca_georgescuLuca Georgescu Luca_georgescu Data 8 noiembrie 2025 09:56:44
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax=2e6+5;
string s,t;
int lps[nmax];

void create_lps(int m)
{
    int i=1, lg=0;
    while ( i<m )
    {
        if ( s[i]==s[lg] )
        {
            lg++;
            lps[i]=lg;
            i++;
        }
        else if ( lg ) lg=lps[lg-1];
        else
        {
            lps[i]=0;
            i++;
        }
    }
}

vector <int> rez;

void kmp(int n, int m)
{
    int lg=0, i=1;
    while ( i<n )
    {
        if ( t[i]==s[lg] )
        {
            lg++; i++;
            if ( lg==m )
            {
                rez.push_back(i-m);
                lg=lps[lg-1];
            }
        }
        else if ( lg ) lg=lps[lg-1];
        else i++;
    }
}

int main()
{
    f >> s >> t;
    create_lps(s.size());

    /*for (int i=0; i<s.size(); i++ )
        cout << lps[i] << " ";*/

    kmp(t.size(),s.size());

    g << rez.size() << '\n';
    for (int idx:rez )
        g << idx << " ";

    return 0;
}