Cod sursa(job #2714279)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 1 martie 2021 17:11:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 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 ;

int  p [ NR ];
int cnt ;
int sol [ NR ] ;
ifstream in ( "strmatch.in" ) ;
ofstream out ( "strmatch.out" ) ;
signed main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);

    in >> s >> t ;
    int L = 0 ;
    for ( int i = 1 ; i < s.size() ; ++ i ) {
        while ( L != 0 && s [ L ] != s [ i ] )  {   //lungimea maxima a unei secvente
            L = p [ L - 1 ] ;                           // din S care se termina in i si totodata incepe in S
        }
        if ( s [ i ] == s [ L ] )   {
            ++ L ;
        }
        p [ i ] = L ;
    }
    L = 0 ;
    for ( int i = 0 ; i < t.size() ; ++ i ) {       // lungimea maxima a unei secvente
        while ( L != 0 && s [ L ] != t [ i ] )         {  // din T se termina in i si incepe in S
            L = p [ L - 1 ] ;
        }
        if ( t [ i ] == s [ L ] )   {
            L ++ ;
        }
        if ( L == s.size() )    {
            sol [ ++ cnt ] = i - s.size() + 1 ;
            L = p [ L - 1 ] ;
        }
    }
    out << cnt << '\n' ;
    for ( int i = 1 ; i <= min ( 1000 , cnt ) ; ++ i )  {
        out << sol [ i ] << ' ' ;
    }
    return 0;
}