Cod sursa(job #2424484)

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

using namespace std;


typedef unsigned long long ULL;


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

    ULL prime = 173;
    ULL modulo = 10000019;
    ULL primePow = 1;
    ULL stringHash = 0;
    ULL substringHash = 0;
    unsigned i;

    for (i = 0; i < _substring.size(); ++i) {
        substringHash = (substringHash * prime + _substring[i]) % modulo;
        stringHash = (stringHash * prime + _string[i]) % modulo;

        if (i > 0) {
            primePow = (primePow * prime) % modulo;
        }
    }

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

    for (i = 0; i < limit; ++i) {
        if (substringHash == stringHash) {
            if (++_count <= 1000) {
                pos.push_back(i);
            }
        }

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

        stringHash = stringHash - (_string[i] * primePow) % modulo + modulo;
        stringHash = stringHash * prime + _string[i + _substring.size()];
        stringHash %= modulo;
    }
}


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