Cod sursa(job #2424485)

Utilizator melutMelut Zaid melut Data 23 mai 2019 06:37:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;


string const inFile = "strmatch.in";
string const outFile = "strmatch.out";


ifstream Read(inFile);
ofstream Write(outFile);


void SubstringMatching(
    string const &_string,
    string const &_substring,
    vector<unsigned> &pos,
    unsigned &_count
) {
    if (_substring.size() > _string.size()) {
        return;
    }

    typedef unsigned long long ULL;

    ULL prime = 173;
    ULL modulo1 = 11654387;
    ULL modulo2 = 51054347;
    ULL primePow1 = 1;
    ULL primePow2 = 1;
    ULL stringHash1 = 0;
    ULL stringHash2 = 0;
    ULL substringHash1 = 0;
    ULL substringHash2 = 0;
    unsigned i;

    for (i = 0; i < _substring.size(); ++i) {
        substringHash1 = (substringHash1 * prime + _substring[i]) % modulo1;
        substringHash2 = (substringHash2 * prime + _substring[i]) % modulo2;

        stringHash1 = (stringHash1 * prime + _string[i]) % modulo1;
        stringHash2 = (stringHash2 * prime + _string[i]) % modulo2;

        if (i > 0) {
            primePow1 = (primePow1 * prime) % modulo1;
            primePow2 = (primePow2 * prime) % modulo2;
        }
    }

    unsigned limit = _string.size() - _substring.size() + 1;

    for (i = 0; i < limit; ++i) {
        if (substringHash1 == stringHash1)
        if (substringHash2 == stringHash2) {
            if (++_count <= 1000) {
                pos.push_back(i);
            }
        }

        if (i == limit - 1) {
            break;
        }

        stringHash1 = stringHash1 - (_string[i] * primePow1) % modulo1 + modulo1;
        stringHash1 = stringHash1 * prime + _string[i + _substring.size()];
        stringHash1 %= modulo1;

        stringHash2 = stringHash2 - (_string[i] * primePow2) % modulo2 + modulo2;
        stringHash2 = stringHash2 * prime + _string[i + _substring.size()];
        stringHash2 %= modulo2;
    }
}


int main() {
    string _substring;
    string _string;
    vector<unsigned> pos;
    unsigned _count = 0;

    Read >> _substring;
    Read >> _string;

    SubstringMatching(_string, _substring, pos, _count);

    Write << _count << '\n';

    for (unsigned i = 0; i < pos.size(); ++i) {
        Write << pos[i] << ' ';
    }

    return 0;
}