Cod sursa(job #2892692)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 23 aprilie 2022 11:28:19
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

#define MAX_N 2000000
#define MAX_SOL 1000

using namespace std;

int z[2 * MAX_N + 1];
vector <int> ans;

int main() {
    ifstream cin( "strmatch.in" );
    ofstream cout( "strmatch.out" );

    int l, r, i;
    string s, pat, text;

    cin >> pat >> text;

    s = pat + '#' + text;

    z[0] = 0;
    l = r = 0;
    for ( i = 1; i < s.size(); i++ ) {
        if ( i <= r )
            z[i] = max( r - i + 1, z[i - l] );
        while ( i + z[i] < s.size() && s[z[i]] == s[i + z[i]] )
            z[i]++;
        if ( i + z[i] - 1 > r ) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    for ( i = 0; i < s.size(); i++ ) {
        if ( z[i] == pat.size() )
            ans.push_back( i - pat.size() - 1 );
    }

    cout << ans.size() << "\n";
    for ( i = 0; i < ans.size() && i < MAX_SOL; i++ )
        cout << ans[i] << " ";

    return 0;
}