Cod sursa(job #1464855)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 25 iulie 2015 17:09:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<cstring>
#define p 97
#define mod1 100007
#define mod2 100021
using namespace std;
int n, m, i, h1, h2, s1, s2, nr, pt1, pt2;
char a[2000005], b[2000005];
int v[1005];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main(){
    fin>> (a + 1);
    n = strlen(a + 1);
    for(i = 1; i <= n; i++){
        s1 = (s1 * p + a[i]) % mod1;
        s2 = (s2 * p + a[i]) % mod2;
    }
    pt1 = pt2 = 1;
    for(i = 1; i < n; i++){
        pt1 = pt1 * p % mod1;
        pt2 = pt2 * p % mod2;
    }
    fin>> (b + 1);
    m = strlen(b + 1);
    for(i = 1; i <= m; i++){
        h1 = (h1 * p + b[i]) % mod1;
        h2 = (h2 * p + b[i]) % mod2;
        if(i >= n){
            if(h1 == s1 && h2 == s2){
                nr++;
                if(nr <= 1000){
                    v[nr] = i - n;
                }
            }
            h1 -= pt1 * b[i - n + 1] % mod1;
            if(h1 < 0){
                h1 += mod1;
            }
            h2 -= pt2 * b[i - n + 1] % mod2;
            if(h2 < 0){
                h2 += mod2;
            }
        }
    }
    fout<< nr <<"\n";
    for(i = 1; i <= min(nr, 1000); i++){
        fout<< v[i] <<" ";
    }
    return 0;
}