Mai intai trebuie sa te autentifici.

Cod sursa(job #2226033)

Utilizator lorena1999Marginean Lorena lorena1999 Data 29 iulie 2018 11:34:51
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define MAX 4000000
#define llu long long unsigned int

using namespace std;

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

string a, b;

queue < llu > q;

map < llu , llu > myMap;

int main()
{
    f>>a>>b;
    llu la = a.size();
    llu lb = b.size();
    llu prime=1;
    llu hashValueA = 0;
    for(int i=0; i<la; i++)
    {
        int ascii = a[i]-'A'+1;
        hashValueA+=ascii*prime;
        prime*=128;
    }
    //cout<<hashValueA<<endl;
    llu c=0;
    llu hashValueB=0;
    prime=1;
    for(int i=0; i<la; i++)
    {
        hashValueB+=(b[i]-'A'+1)*prime;
        prime*=128;
    }
    prime/=128;
    for(int i=la; i<lb; i++)
    {
        //cout<<hashValueB<<endl;
        if(hashValueB==hashValueA)
            q.push(i-la);
        hashValueB-=(b[i-la]-'A'+1);
        hashValueB/=128;
        hashValueB+=(b[i]-'A'+1)*prime;
    }
    //cout<<hashValueB<<endl;
    if(hashValueA==hashValueB)
        q.push(lb-la);
    g<<q.size()<<'\n';
    while(!q.empty())
    {
        llu x = q.front();
        g<<x<<" ";
        q.pop();
    }
}