Cod sursa(job #2713987)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 1 martie 2021 01:54:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
/*
*  Created by Andrei Arhire 01/03/2021
*  Copyright © 2021 Andrei Arhire. All rights reserved.
*  Expected verdict - Accepted
*/
#include <bits/stdc++.h>

#define pb push_back
#define zero(pos) pos&(-pos)
#define eb emplace_back
#define mp make_pair
using namespace std;
const long long NR = 2e6 + 1e2;
const long long oo = 1e16 ;


string s , t ;
vector < int > sol , P ( NR , 0 ) ;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
signed main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);
    in >> s >> t ;
    int i , L = 0 ;
    for ( i = 1 ; i < s.size() ; ++ i ) {
        while ( L && s [ i ] != s [ L ] )  {
            L = P [ L - 1 ] ;
        }
        if ( s [ i ] == s [ L ] )   {
            ++ L ;
        }
        P [ i ] = L ;
    }
    L = 0 ;
    for ( i = 0 ; i < t.size() ; ++ i ) {
        while ( L && t [ i ] != s [ L ] )   {
            L = P [ L - 1 ] ;
        }
        if ( t [ i ] == s [ L ] )   {
            ++ L ;
        }
        if ( L == s.size() )    {
            sol.pb(i+1-L);
            L = P [ L - 1 ] ;
        }
    }
    out << sol.size() << '\n' ;
    for ( i = 0 ; i < min ( ( int ) sol.size() , 1000 ) ; ++ i )    {
        out << sol [ i ] << ' ' ;
    }
    return 0;
}