Cod sursa(job #3297277)

Utilizator Arhiva_EducationalaArhiva Educationala Arhiva_Educationala Data 22 mai 2025 13:00:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e6;

int kmp[NMAX + 1];



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

    string s1, s2, s;
    fin >> s1 >> s2;
    s = "#" + s1 + "#" + s2;

    kmp[1] = 0;
    for ( int i = 2; i < (int) s.size(); i ++ ) {
        int x = kmp[i - 1];
        while ( x != 0 && s[x + 1] != s[i] ) {
            x = kmp[x];
        }
        if ( s[x + 1] == s[i] ) {
            kmp[i] = x + 1;
        } else {
            kmp[i] = 0;
        }
    }
    vector <int> ans;
    for ( int i = 1; i <= (int)s.size(); i ++ ) {
        if ( kmp[i] == (int)s1.size() ) {
            ans.push_back( i );
        }
    }
    fout << ans.size() << '\n';
    for ( int i = 0; i < min( (int)ans.size(), 1000 ); i ++ ) {
        fout << ans[i] - 2 * (int)s1.size() - 1 << ' ';
    }
    fout << '\n';
    return 0;
}