Cod sursa(job #856673)

Utilizator SovStoStoicescu Mihail Cristian SovSto Data 16 ianuarie 2013 20:38:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include<string.h>
#define mod1 666001
#define mod2 100007
 
using namespace std;
FILE *f = fopen("strmatch.in","r"), *g = fopen("strmatch.out","w");
 
char s[2000001], v[2000001];
int i, j, nrv1 = 0, nrs1 = 0, nrv2 = 0, nrs2 = 0, p1 = 1, p2 = 1, lv, ls, poz[2000001], npoz=0;
int main()
{
     
    fscanf(f, "%s%s", &v, &s);
     
    lv = strlen(v);
    ls = strlen(s);
     
    for(i = 0; i < lv; i++)
    {
        nrv1 = ( nrv1 * 73 + v[i] ) % mod1;
        nrv2 = ( nrv2 * 73 + v[i] ) % mod2;
         
        nrs1 = ( nrs1 * 73 + s[i] ) % mod1;
        nrs2 = ( nrs2 * 73 + s[i] ) % mod2;
         
        if(i)
        {
            p1 = ( p1 * 73 ) % mod1;
            p2 = ( p2 * 73 ) % mod2;
        }
         
    }
     
    if( nrv1 == nrs1 &&   nrv2 == nrs2)
        poz[++npoz] = 0;
     
    for(i = lv; i < ls; i++)
    {
        nrs1 = ( ( nrs1 - ( s[i-lv] * p1 ) % mod1 + mod1 ) * 73 + s[i] ) % mod1;
        nrs2 = ( ( nrs2 - ( s[i-lv] * p2 ) % mod2 + mod2 ) * 73 + s[i] ) % mod2;
         
        if( nrv1 == nrs1 &&   nrv2 == nrs2)
            poz[++npoz] = i - lv + 1;
    }
     
    fprintf(g, "%d\n", npoz);
     
    for( i = 1; i <= npoz && i<=1000; i++ )
        fprintf(g, "%d ", poz[i]);
     
    return 0;
}