Cod sursa(job #2388335)

Utilizator AkrielAkriel Akriel Data 25 martie 2019 22:07:54
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>

using namespace std;

string text;
string pattern;

const int base = 256;
const int prime = 101;

int computeHash(string text, int length){
    int hash = 0;
    for (int index = 0; index < length; index++){
        hash *= 256;
        int letter = text[index];
        hash += letter;
        hash %= prime;
    }

    if (hash < 0)
        hash += prime;

    return hash;
}

const long long offSet = (((base%prime)*base)%prime);

int nextHash(long long hash, int newPos, string text, int length){
    int oldPos = newPos-length;
    hash += prime;

    hash -= text[oldPos]*offSet;

    hash *= base;

    hash += text[newPos];

    hash %= prime;

    if (hash < 0)
        hash += prime;

    return hash;
}

vector <int> matches;

bool checkMatch(string text, string pattern, int pos){
    for (int i = 0; i < pattern.size(); i++){
        if (text[i+pos] != pattern[i])
            return false;
    }
    return true;
}

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int main() {
    fin >> pattern;
    fin >> text;

    int patternHash = computeHash(pattern, pattern.size());

    int currentHash = computeHash(text, pattern.size());

    if (patternHash == currentHash)
        if (checkMatch(text, pattern, 0))
            matches.push_back(0);

    for (int index = 1; index <= text.size()-pattern.size(); index++){
        currentHash = nextHash(currentHash, index+pattern.size()-1, text, pattern.size());

        if (patternHash == currentHash){
            if (checkMatch(text, pattern, index))
                matches.push_back(index);
        }
    }

    fout << matches.size() << "\n";
    int index = 0;
    for (auto it : matches){
        fout << it << " ";
        if (index == 1000)
            break;
    }
}