Cod sursa(job #1968483)

Utilizator robx12lnLinca Robert robx12ln Data 17 aprilie 2017 18:37:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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{
            if( z[i - st] < dr - i + 1 ){
                z[i] = z[i - st];
            }else{
                z[i] = dr - i + 1;
                int poz = z[i];
                int nr = 0;
                while( s[poz] == s[i + poz] && poz <= n ){
                    nr++;
                    poz++;
                }
                z[i] += nr;
                st = i;
                dr = i + z[i] - 1;
            }
        }
        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;
}