Cod sursa(job #913617)

Utilizator MciprianMMciprianM MciprianM Data 13 martie 2013 17:22:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <cassert>
#include <vector>
#include <cstring>
//#include <iostream>
  
using namespace std;
  
static const int MOD = 666013, A = 62, MAXL = 2222222;
int v[1009];
char s1[MAXL], s2[MAXL];
  
inline int dig(char c) {
    int ans = 0;
    assert(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9'));
    if(c >= 'a') {
        ans = (c - 'a') + 36;
    }
    else if(c >= 'A') {
        ans = (c - 'A') + 10;
    }
    else {
        ans = (c - '0');
    }
    return ans;
}
  
int main() {
    int i, kt = 0;
    ifstream f("strmatch.in");
    f >> s2 >> s1;
    f.close();
    //cout << s2 << endl;
    //cout << s1 << endl;
    ofstream g("strmatch.out");
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    if(n1 < n2) {
        g << "0\n";
    }
    else {
        int j, hP(0), hT(0), Ap = 1;
        for(i = 0; s2[i]; i++) {
            hP = (hP * A + dig(s2[i])) % MOD;
            //cout << dig(s2[i]) << endl;
        }
        //cout << hP << endl;
        int l = n2 - 1;
        for(i = 0; i < l; i++) {
            hT = (hT * A + dig(s1[i])) % MOD;
            //cout << hT << endl;
            Ap = (Ap * A) % MOD;
        }
        for(i = l; s1[i]; i++) {
            hT = ((hT * A) + dig(s1[i])) % MOD;
            //cout << hT << endl;
            if(hT == hP) {//possible match
                for(j = 0; s2[j]; j +=  max(1, n2 / 10)) {
                    if(s2[j] != s1[i - l + j]) {
                        break;
                    }
                }
                if(!s2[j]) {
                    if(kt < 1000) {
                        v[kt] = i - l;
                    }
                    kt++;
                }
            }
            hT -= dig(s1[i - l]) * Ap;
            hT = hT % MOD;
            if(hT < 0)   hT += MOD;
        }
        g << kt << '\n';
        for(i = 0; i < min(1000, kt); i++) {
            g << v[i] << ' ';
        }
        if(kt)    g << '\n';
    }
    g.close();
    return 0;
}