Cod sursa(job #1745984)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 22 august 2016 16:41:43
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.77 kb
# include <iostream>
# include <fstream>

# include <vector>

# include <cstring>

using namespace std;

# define MAX_LEN 2000001

int pi[MAX_LEN];

char a[1 + MAX_LEN];
char b[1 + MAX_LEN];

vector<int> rez;

int main() {
    ifstream fin( "strmatch.in" );
    ofstream fout( "strmatch.out" );
    int i, k, r, n, m;

    fin >> a + 1 >> b + 1;
    n = strlen( a + 1 );
    m = strlen( b + 1 );

    pi[0] = -1;
    k = r = 0;
    for ( i = 1; i <= m; i ++ ) {
        while ( k != -1 && b[i] != a[k + 1] )
            k = pi[k];

        k ++;
        pi[i] = k;

        if ( k == n )
            rez.push_back( i - n );
    }

    fout << rez.size() << endl;
    for ( i = 0; i < rez.size(); i ++ )
        fout << rez[i] << ' ';


    fin.close();
    fout.close();

    return 0;
}