Cod sursa(job #1804974)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 13 noiembrie 2016 12:39:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

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

string a, b;
pair<int, int> code;
const int MOD1 = 17;
const int MOD2 = 2999999;
const int base = 30;

vector<int> sol;

void CodeA()
{
    for(int i = 0; i < a.size(); ++i)
    {
        code.first = code.first * base + a[i];
        code.first %= MOD1;

        code.second = code.second * base + a[i];
        code.second %= MOD2;
    }
}

void rezolvare()
{
    if(a.size() > b.size())
    {
        out << 0;
        return;
    }
    CodeA();
    pair<int, int> cCode = make_pair(0, 0); //current code
    int i;
    int pow1 = 1, pow2 = 1;
    for(i = 0; i < a.size(); ++i)
    {
        cCode.first = cCode.first * base + b[i];
        cCode.first %= MOD1;

        cCode.second = cCode.second * base + b[i];
        cCode.second %= MOD2;

        if(i > 0)
        {
            pow1 = (pow1 * base) % MOD1;
            pow2 = (pow2 * base) % MOD2;
        }
    }
    while(i < b.size())
    {
        if(code == cCode)
            sol.push_back(i - a.size());

        cCode.first = (cCode.first - (b[i - a.size()] * pow1) % MOD1) * base + b[i];
        if(cCode.first < 0)
            cCode.first += MOD1;
        else
            cCode.first %= MOD1;

        cCode.second = (cCode.second - (b[i - a.size()] * pow2) % MOD2) * base + b[i];
        if(cCode.second < 0)
            cCode.second += MOD2;
        else
            cCode.second %= MOD2;

        ++i;
    }
}

void afisare()
{
    out << sol.size() << "\n";
    for(auto x:sol)
        out << x << " ";
}

int main()
{
    in >> a >> b;
    rezolvare();
    afisare();
    return 0;
}