Cod sursa(job #1641213)

Utilizator RaTonAndrei Raton RaTon Data 8 martie 2016 21:44:41
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
#define mx 2000001
#define prim 666013
char c[mx], s[mx];
int  rez[1000], nr, n, m;

int exp(int b,int p){
    int r;
    r = 1;
    while( p > 0 ){
        if ( p % 2 == 1 )
            r = (r * b) % prim;
        b = (b * b) % prim;
        p /= 2;
    }
    return r;
}

int check( int poz ){
    int j;
    j = 0;
    while( s[poz] == c[j] && j < n ){
        j++;
        poz++;
    }
    if( j == n )
        return 1;
    else
        return 0;
}

int main()
{
    int p, t, dc, ds, pow, r, a, ok, poz, i;
    fi.get(c,mx);
    fi.get();
    fi.get(s,mx);
    //fo << c << "\n" << s;
    n = strlen(c);
    p = 0;
    t = 0;
    for( i = 0; i < n; i++ ){
        if( islower(c[i]) ){
            dc = c[i] - 'a';
        }
        else{
            dc = c[i] - 'A' + 26;
        }
        if( dc > 0 ){
            pow = (exp(51,n-i-1) * dc) % prim;
            p = (p + pow) % prim;
        }

        if( islower(s[i]) ){
            ds = s[i] - 'a';
        }
        else{
            ds = s[i] - 'A' + 26;
        }

        if( ds > 0 ){
            pow = (exp(51,n-i-1) * ds) % prim;
            t = (t + pow) % prim;
        }
    }

    nr = 0;
    if( p == t )
        if( check(0) == 1 )
            rez[nr++] = 0;

    m = strlen(s);
    for( i = n; i < m; i++ ){
        poz = i - n;
        if( islower(s[poz]) )
            ds = s[poz] - 'a';
        else
            ds = s[poz] - 'A' + 26;
        //if( ds > 0 ){
            pow = (exp(51,n-1) * ds) % prim;
            t = (t - pow) % prim;
      //  }

        if( islower(s[i]) )
            ds = s[i] - 'a';
        else
            ds = s[i] - 'A' + 26;
        t = (t * 51) % prim;
        t = (t + ds) % prim;
        if( t == p )
            if(check(poz + 1) == 1)
                rez[nr++] = poz + 1;
    }
    fo << nr << "\n";
    for( i = 0; i < nr && i < 1000; i++ )
        fo << rez[i] << " ";

    return 0;
}