Cod sursa(job #171753)

Utilizator igorPirnau Igor igor Data 4 aprilie 2008 23:57:15
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<fstream.h>

ofstream g("strmatch.out");
#define nmax 2000100
#define rest 67

int nr, k, l, b, val, val2, s[1010];
char s1[nmax], s2[nmax];

void citire()
{
    ifstream f("strmatch.in");
    f.getline( s1, nmax);
    f.getline( s2, nmax);
    f.close();
}

void calc_s1()
{
    int i;

    b = 1;
    k = strlen (s1);
    for(i=k-1; i>=0; --i){
        val = ( val + b * ( s1[i] % rest ) ) % rest;
        b = ( b * rest ) % rest;
    }
}

int cmp(int x)
{
    int i;
    for(i=0; i<k; ++i) if( s1[i] != s2[i+x-k+1] ) return 0;
    return 1;
}

void rezolva()
{
    int x, i;

    x = b;
    for(i=0; i<k; ++i){
        val2 = ( val2 + x * ( s2[i] % rest ) ) % rest;
        x = ( x / rest ) % rest;
    } 
    
    if( val2 == val ) s[++nr] = 0;
    l = strlen (s2);
    for( ; i<l; ++i){
        val2 = ( val2 - ( b * s2[l-k] ) % rest ) % rest;
        val2 = ( val2 * rest ) % rest;
        val2 = ( val2 + s2[i] ) % rest;
        if( val2 == val ) if( cmp(i) ) s[++nr] = i - k + 1;
    }
    
    g<<nr<<'\n';
    if ( nr < 1000 ) for(i=1; i<=nr; ++i) g<<s[i]<<' ';
        else for(i=1; i<=1000; ++i) g<<s[i]<<' ';
}   
  
int main()
{
    citire();
    calc_s1();
    rezolva();
    g.close();
    return 0;
}