Cod sursa(job #1901575)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 4 martie 2017 09:33:21
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

fstream in ( "strmatch.in" , ios::in  );
fstream out( "strmatch.out", ios::out );

const int DIM = 4e6;

vector<int> lst;
int z[DIM]; char str[DIM];

int main( void ) {
    ios::sync_with_stdio( false );
    
    in >> ( str + 1 ); int n = (int) strlen( str + 1 );
    in >> ( str + n + 1 ); int m = (int) strlen( str + n + 1 );
    
    int ans = 0; z[1] = n + m;
    for( int k = 2, l = 1, r = 1; k <= n + m; k ++ ) {
        if( k > r ) {
            int i = 1;
            while( str[i] == str[k + i - 1] && k + i - 1 <= n + m )
                i ++;
            
            z[k] = i - 1;
            
            l = k;
            r = k + z[k] - 1;
        }
        else {
            int k2 = k - l + 1;
            
            if( z[k2] < r - k + 1 )
                z[k] = z[k2];
            else {
                int i = r - k + 1;
                while( str[i] == str[k + i - 1] && k + i - 1 <= n + m )
                    i ++;
                
                z[k] = i - 1;
                
                l = k;
                r = k + z[k] - 1;
            }
        }
        
        if( z[k] >= n && k > n ) {
            ans ++;
            
            if( lst.size() < 1000 )
                lst.push_back( k - n - 1 );
        }
    }

    out << ans << endl;
    for( int x : lst )
        out << x << " ";
    out << endl;
    
    return 0;
}