Cod sursa(job #3163466)

Utilizator elisa.ipateElisa Ipate elisa.ipate Data 31 octombrie 2023 14:58:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <vector>
#include <fstream>



using namespace std;

#define nmax

int pi[5000000];

vector <int> v;

int main() {
    string a, b, s;
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    int i, k;
    cin >> a >> b;
    k = 0;
    s = a + '#' + b;
    for( i = 1; i < s.size(); i++ ) {
        while( k != 0 && s[k] != s[i] )
            k = pi[k-1];
        if( s[k] == s[i] )
            k++;
        pi[i] = k;
        //cout << k << " ";
        if( k == a.size() )
            v.push_back( i - 2*a.size() );
    }
    //cout < "\n";
    cout << v.size() << "\n";
    for( i = 0; i < v.size(); i++ )
        cout << v[i] << " ";

    return 0;
}