Cod sursa(job #2892687)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 23 aprilie 2022 10:49:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

#define MAX_N 2000000
#define MAX_SOL 1000

using namespace std;

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

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

    int i;
    string s, pat, text;

    cin >> pat >> text;

    s = pat + '#' + text;

    lps[0] = 0;
    for ( i = 1; i < s.size(); i++ ) {
        lps[i] = lps[i - 1];
        while ( lps[i] > 0 && s[i] != s[lps[i]] )
            lps[i] = lps[lps[i] - 1];
        if ( s[i] == s[lps[i]] )
            lps[i]++;
    }

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

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

    return 0;
}