Cod sursa(job #2809053)

Utilizator Tudor06MusatTudor Tudor06 Data 25 noiembrie 2021 21:04:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

const int NMAX = 2e6;

int z[2 * NMAX + 1];

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

void calculate_z( const string& s ) {
    int i, l, r, n = s.size();
    l = r = 0;
    for ( i = 1; i < n; i ++ ) {
        if ( r < i ) {
            l = r = i;
            while ( r < n && s[r - l] == s[r] )
                r ++;
            z[i] = r - l;
            r --;
        } else {
            int aux = i - l;
            if ( z[aux] <= r - i )
                z[i] = z[aux];
            else {
                l = i;
                while ( r < n && s[r] == s[r - l] )
                    r ++;
                z[i] = r - l;
                r --;
            }
        }
    }
}
vector <int> ans;

void solve() {
    int cnt = 0;
    string s1, s2;
    fin >> s1 >> s2;
    s2 = s1 + '#' + s2;
    calculate_z( s2 );
    for ( int i = s1.size(); i < s2.size(); i ++ ) {
        if ( z[i] == s1.size() ) {
            cnt ++;
            if ( ans.size() < 1000 )
                ans.push_back( i );
        }
    }
    fout << cnt << '\n';
    for ( int i = 0; i < ans.size(); i ++ )
        fout << ans[i] - s1.size() - 1 << ' ';
}

int main() {
    solve();
    return 0;
}