Cod sursa(job #2142408)

Utilizator c0mradec0mrade c0mrade Data 24 februarie 2018 23:17:52
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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;
    int ans=0;
    if(hasha==hashb)
    {
        sol.push_back(0);
        ans++;
    }

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

        }
    }

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

    for(int i = 0 ; i < 1000 ; i++)
    {
        out<<sol[i]<<" ";

    }
    out.close();
}