Cod sursa(job #2306015)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 21 decembrie 2018 15:10:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#define NMAX  2000000
#define END 1000

using namespace std;

string a, b;
vector <int> ans;
int pi[1 + NMAX];

int main() {
    freopen ( "strmatch.in", "r", stdin );
    freopen ( "strmatch.out", "w", stdout );

    int p;

    cin >> a >> b;

    int k = 0;

    for ( int i = 1; i < a.size(); i++ ) {
        while ( k > 0 && a[k] != a[i] )
            k = pi[k - 1];

        if ( a[k] == a[i] )
            k++;

        pi[i] = k;
    }

    k = 0;

    for ( int i = 0; i < b.size(); i++ ) {
        while ( k > 0 && a[k] != b[i] )
            k = pi[k - 1];

        if ( a[k] == b[i] )
            k++;

        if ( k == a.size() ) {
            if ( ans.size() < END )
                ans.push_back ( i - a.size() + 1 );
            else
                ans.push_back ( -1 );
        }
    }

    cout << ans.size() << endl;

    for ( vector<int>::iterator it = ans.begin(); it != ans.end() && *it != -1; it++ )
        cout << *it << ' ';

    return 0;
}