Cod sursa(job #3321090)

Utilizator octavurlurleteanu alexandru octavian octavurl Data 8 noiembrie 2025 10:27:38
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 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;
int nr = 0 ;
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 ;
    }
}

signed main()
{
    string s;
    fin >> s ;
    string t ;
    fin >> t ;
    llps(s);
    idiot(t,s);

    fout << ans.size() << '\n';
    int nr = 0 ;
    for ( auto it : ans )
        {
            ++nr;
            if ( nr == 1001 )
                break;
            fout << it << ' ' ;
        }
    return 0;
}