Cod sursa(job #2613835)

Utilizator Katherine456719Swan Katherine Katherine456719 Data 10 mai 2020 18:40:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
string a,b;
unsigned int baz=317;
unsigned int ha[200001],puteri[2000001],hasha;
int rez[1001],cont;
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>a>>b;
    for(int i=a.size()-1; i>=0; i--)
        hasha=(hasha*baz+a[i]);
    for(int i=b.size()-1; i>=0; i--)
        ha[i]=(ha[i+1]*baz+b[i]);
    puteri[0]=1;
    for(int i=1; i<b.size(); ++i)
        puteri[i]=(puteri[i-1]*baz);
    for(int i=a.size()-1; i<b.size(); i++)
        if(hasha== (ha[i-a.size()+1]-ha[i+1]*puteri[a.size()]))
            rez[++cont]=i-a.size()+1;
    cout<<cont<<"\n";
    for(int i=1; i<=cont and i<=1000; i++)
        cout<<rez[i]<<" ";
    return 0;
}