Cod sursa(job #2142035)

Utilizator c0mradec0mrade c0mrade Data 24 februarie 2018 18:05:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

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

{
    int base=3,shift=1;;

    string a,b;

    cin>>a>>b;
     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);
        }
    }

    cout<<sol.size()<<'\n';

    for(auto it:sol)
    {
        cout<<it<<" ";
    }
}