Cod sursa(job #1968468)

Utilizator robx12lnLinca Robert robx12ln Data 17 aprilie 2017 18:28:04
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<cstring>
#include<vector>
#define DIM 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2 * DIM], s1[DIM];
int n, st, dr, z[DIM], lg;
vector<int> sol;
int main(){
    fin >> s;
    lg = strlen( s );
    fin >> s1;
    strncat( s, s1, sizeof(s1) );
    n = strlen( s ) - 1;
    z[0] = 0;
    st = dr = 0;
    for( int i = 1; i <= n; i++ ){
        if( i > dr ){
            int poz = 0;
            while( s[poz] == s[i + poz] && poz <= n ){
                poz++;
            }
            st = i;
            dr = poz + st - 1;
            z[i] = poz;
        }else{
            z[i] = z[i - st];
            if( z[i] == 0 ){
                st = dr = i;
                continue;
            }
            int poz = i - st + z[i];
            int nr = 0;
            while( s[poz] == s[i + poz] && poz <= n ){
                nr++;
                poz++;
            }
            poz--;
            z[i] += nr;
        }
        if( sol.size() >= 1000 )
            break;
        if( i >= lg && z[i] >= lg ){
            sol.push_back( i - lg );
        }
    }
    fout << sol.size() << "\n";
    for( int i = 0; i < sol.size(); i++ ){
        fout << sol[i] << " ";
    }
    return 0;
}