Cod sursa(job #2143077)

Utilizator rnqftwcalina florin daniel rnqftw Data 25 februarie 2018 16:05:43
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
vector<int> sol;
const int x=47,y=73;
#define mod 666
int main()

{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    int shift1=1,shift2=1;

    string a,b;

     in>>a>>b;
     in.close();

    int n=a.size();
    ull hasha1=0,hashb1=0,hasha2=0,hashb2=0;

    for(int i = 0 ; i <n;i++)
    {
         if(i!=0){
            shift1*=x;
            shift2*=y;
        }
        hasha1+=a[i]*shift1;
        hasha2+=a[i]*shift2;
        hashb1+=b[i]*shift1;
        hashb2+=b[i]*shift2;


    }

    if(hasha1==hashb1 && hasha2==hashb2)
    {
        sol.push_back(0);

    }

    for(int i = n ; i< b.size() ; i ++)
    {
        hashb1-=b[i-n];
        hashb1/=x;
        hashb1+=b[i]*shift1;
        hashb2-=b[i-n];
        hashb2/=y;
        hashb2+=b[i]*shift2;
         if(hasha1==hashb1 && hasha2==hashb2)
        {

            sol.push_back(i-n+1);
        }
    }

    out<<sol.size()<<'\n';
     int limit=min(1000,int(sol.size()));
    for(int i = 0 ; i < limit ;i++)
    {
        out<<sol[i]<<" ";
    }
    out.close();
    return 0;
}