Cod sursa(job #1793315)

Utilizator GrandmasterSoucup Bogdan Grandmaster Data 30 octombrie 2016 21:47:42
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
//#include <unordered_map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
#include <bitset>
#include <map>
#define MAX 500000000000
//#include <iostream>
//#include <windows.h>
#include <deque>
using namespace std;
//ifstream cin("jocul.in");
//ofstream cout("jocul.out");
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int val = 0, prime = 61, index = 1;
int hash_cal(string p)
{
    for(int i = 0; i < p.size(); i++)
    {
        val += index * (p[i] - 52);
        index *= prime;
    }
    return val;
}
void recalc_hash(string p, vector<int> &x, int indexx)
{
    int sum = 1, val = 0;
    for(int i = 0; i <= indexx; i++)
    {
        val += (sum * (p[i] - 52));
        sum *= prime;
    }
    sum /= 61;
    x.push_back(val);
    for(int i = indexx + 1; i < p.size(); i++)
    {
        int curr = (val - (p[i - indexx - 1] - 52));
        curr /= 61;
        curr += (p[i] - 52) * sum;
        val = curr;
        x.push_back(curr);
    }
}
int main()
{
    string s, p;
    cin >> s >> p;
    int valor = hash_cal(s);
    vector<int> x, y;
    recalc_hash(p, x, s.size() - 1);
    for(int i = 0; i < x.size(); i++)
        if(x[i] == valor)
           y.push_back(i);
    cout << y.size() << "\n";
    for(int i = 0; i < y.size(); i++)
        cout << y[i] << " ";
    return 0;
}