Cod sursa(job #3163474)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 31 octombrie 2023 15:03:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 2e6;
int p[N], ans[N];

int main () {
    
    string a, b, s;
    
    fin >> a >> b;
    
    s = a + "#" + b;
    
    int k = 0;
    for ( int i = 1; i < s.size(); i++ ) {
        while ( k != 0 && s[k] != s[i] )
            k = p[k - 1];
        if ( s[k] == s[i] )
            k++;
        p[i] = k;
    }
    
    k = 0;
    int cnt = 0;
    for ( int i = 0; i < s.size(); i++ ) {
        if ( p[i] == a.size() ) {
            cnt++;
            if ( k <= 1000 ) {
                ans[k] = i - 2 * a.size();
                k++;
            }
        }
    }
    
    fout << cnt << "\n";
    
    for ( int i = 0; i < k; i++ )
        fout << ans[i] << " ";
    
    return 0;
}