Cod sursa(job #2949292)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 30 noiembrie 2022 13:17:51
Problema Potrivirea sirurilor Scor 58
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>

using namespace std;
const int nmax = 2e6;
int pi[2 * nmax + 1];
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
int main() {
    string s, s2;
    int n, m;
    fin >> s >> s2;
    n = s.size ();
    m = s2.size ();
    s = s + '#' + s2;

    for ( int i = 1; i < n + 1 + m; i++ ) {
        int j = pi[i - 1];
        while ( j > 0 && s[i] != s[j] )
            j = pi[j - 1];
        if ( s[i] == s[j] )
            j++;
        pi[i] = j;
    }

    int cnt = 0;
    for ( int i = n + 1; i < n + 1 + m; i++ )
        if ( pi[i] == n )
            cnt++;

    fout << cnt << '\n';

    cnt = 0;
    for ( int i = n + 1; i < n + m; i++ )
        if ( pi[i] == n && cnt < 1000 ) {
            fout << ( i - ( n + 1 ) ) - n + 1 << ' ';
            cnt++;
        }


    return 0;
}