Cod sursa(job #2153106)

Utilizator DawlauAndrei Blahovici Dawlau Data 5 martie 2018 22:48:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include<fstream>
#include<cstring>
#include<ctime>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXLEN = 2e6 + 5, ALPHSZ = 73;
const int hashPrime1 = 100007, hashPrime2 = 100021;

char text[MAXLEN], pattern[MAXLEN];
int  matches[1005];
int textLen, patternLen, patternHash1, patternHash2, textHash1, textHash2, MaxPwr1, MaxPwr2, matchesLen, matchesCnt;

inline void getMaxPwr(){

    MaxPwr1 = 1;
    MaxPwr2 = 1;
    int exponent;
    for(exponent = 1; exponent < patternLen; ++exponent){

        MaxPwr1 = (1ULL * MaxPwr1 * ALPHSZ) % hashPrime1;
        MaxPwr2 = (1ULL * MaxPwr2 * ALPHSZ) % hashPrime2;
    }
}

inline void getPatternHashes(){

    int idx;
    for(idx = 1; idx <= patternLen; ++idx){

        patternHash1 = ((1ULL * patternHash1 * ALPHSZ) % hashPrime1 + pattern[idx]) % hashPrime1;
        patternHash2 = ((1ULL * patternHash2 * ALPHSZ) % hashPrime2 + pattern[idx]) % hashPrime2;
    }
}

inline void getTextHashes(){

    int idx;
    for(idx = 1; idx < patternLen; ++idx){

        textHash1 = ((1ULL * textHash1 * ALPHSZ) % hashPrime1 + text[idx]) % hashPrime1;
        textHash2 = ((1ULL * textHash2 * ALPHSZ) % hashPrime2 + text[idx]) % hashPrime2;
    }
}

inline void findMatches(){

    int idx;
    for(idx = patternLen; idx <= textLen; ++idx){

        textHash1 = ((1ULL * textHash1 * ALPHSZ) % hashPrime1 + text[idx]) % hashPrime1;
        textHash2 = ((1ULL * textHash2 * ALPHSZ) % hashPrime2 + text[idx]) % hashPrime2;

        if(textHash1 == patternHash1 and textHash2 == patternHash2){
            ++matchesCnt;
            if(matchesLen < 1000)
                matches[++matchesLen] = idx - patternLen;
        }

        textHash1 = textHash1 - ((1ULL * MaxPwr1 * text[idx - patternLen + 1]) % hashPrime1) + hashPrime1;
        textHash2 = textHash2 - ((1ULL * MaxPwr2 * text[idx - patternLen + 1]) % hashPrime2) + hashPrime2;
    }
}

inline void printMatches(){

    int idx;
    fout << matchesCnt << '\n';
    for(idx = 1; idx <= matchesLen; ++idx)
        fout << matches[idx] << ' ';
}

int main(){

    fin >> (pattern + 1) >> (text + 1);
    patternLen = strlen(pattern + 1);
    textLen = strlen(text + 1);

    if(patternLen > textLen){
        fout << 0;
        return 0;
    }

    getMaxPwr();
    getPatternHashes();
    getTextHashes();
    findMatches();
    printMatches();
}