Cod sursa(job #2231662)

Utilizator lorena1999Marginean Lorena lorena1999 Data 15 august 2018 15:33:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

string a, b;

int la, lb;

queue < ll > q;

ll hashA, hashB;

ll hashValue(int u, int v, string x)
{
    int hV=0;
    for(int i=u; i<=v; i++)
        hV+=(int)x[i];
    return hV;
}

bool match(int start)
{
    for(int i=0; i<la; i++)
        if(a[i]!=b[start++])
            return false;
    return true;
}

int main()
{
    /*for(char i='A'; i<='C'; i++)
        cout<<(int)i<<endl;
    cout<<endl;*/
    f>>a>>b;
    la = a.length();
    lb = b.length();
    hashA = hashValue(0, la-1, a);
    hashB = hashValue(0, la-2, b);
    //cout<<hashA<<" "<<hashB<<endl;
    for(int i=la-1; i<lb; i++)
    {
        //cout<<"Punem "<<i<<endl;
        hashB+=(int)b[i];
        if(hashA==hashB)
            if(match(i-la+1))
                q.push(i-la+1);
        hashB-=(int)b[i-la+1];
        //cout<<"Scadem "<<i-la+1<<endl;
    }
    g<<q.size()<<'\n';
    while(!q.empty())
    {
        int nr = q.front();
        g<<nr<<" ";
        q.pop();
    }
}