Cod sursa(job #2153190)

Utilizator DawlauAndrei Blahovici Dawlau Data 6 martie 2018 00:35:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.54 kb
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXLEN = 2e6 + 5, ALPHSZ = 75;
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 getHashes(){

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

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

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

        MaxPwr1 = (MaxPwr1 * ALPHSZ) % hashPrime1;
        MaxPwr2 = (MaxPwr2 * ALPHSZ) % hashPrime2;
    }
    patternHash1 = ((patternHash1 * ALPHSZ) % hashPrime1 + pattern[patternLen]) % hashPrime1;
    patternHash2 = ((patternHash2 * ALPHSZ) % hashPrime2 + pattern[patternLen]) % hashPrime2;

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

inline void findMatches(){

    int idx;

    if(textHash1 == patternHash1 and textHash2 == patternHash2){

        ++matchesCnt;
        matches[++matchesLen] = 0;
    }
    for(idx = patternLen + 1; idx <= textLen; ++idx){

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

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

        if(textHash1 == patternHash1 and textHash2 == patternHash2){

            ++matchesCnt;
            if(matchesLen < 1000)
                matches[++matchesLen] = idx - patternLen;
        }
    }
}

inline void printMatches(){

    fout << matchesCnt << '\n';

    int idx;
    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;
    }

    getHashes();
    findMatches();
    printMatches();
}