Cod sursa(job #2142810)

Utilizator rnqftwcalina florin daniel rnqftw Data 25 februarie 2018 12:55:39
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
vector<int> sol;
int main()

{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    int base=3,shift=1;;

    string a,b;

     in>>a>>b;
     in.close();
     int n=a.size();
    ull hasha=0,hashb=0;

    for(int i = 0 ; i <n;i++)
    {
        hasha+=a[i]*pow(3,i);
        hashb+=b[i]*pow(3,i);
        shift*=3;
    }
    shift/=3;
    if(hasha==hashb)
    {
        sol.push_back(0);

    }

    for(int i = n ; i< b.size() ; i ++)
    {
        hashb-=b[i-n];
        hashb/=3;
        hashb+=b[i]*shift;
        if(hasha == hashb)
        {

            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;
}