Cod sursa(job #2142042)

Utilizator c0mradec0mrade c0mrade Data 24 februarie 2018 18:13:47
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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';

    for(auto it:sol)
    {
        out<<it<<" ";
    }
    out.close();
}