Cod sursa(job #3321079)

Utilizator octavurlurleteanu alexandru octavian octavurl Data 8 noiembrie 2025 10:21:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

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

unordered_map<int,int>lps;
void llps ( string s )
{
    int i = 1  , m = s.size() , lg = 0 ;
    lps[0] = 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>ans;
void idiot ( string s , string t )
{
    int i = 0 , lg =  0 , n = s.size() , m = t.size() ;
    while ( i < n )
    {
    if ( s[i] == t[lg] )
    {
        ++lg;
        ++i;
        if (lg==m)
        {
            ans.push_back(i-lg);
            lg=lps[lg-1];
        }
    }
    else if ( lg )
        lg = lps[lg-1];
    else
        ++ i ;
    if ( ans.size() > 1000 )
            return ;
    }
}

signed main()
{
    string s;
    fin >> s ;
    string t ;
    fin >> t ;
    llps(s);
    idiot(t,s);
    fout << ans.size() << '\n';
    for ( auto it : ans )
        fout << it << ' ' ;
    return 0;
}