Cod sursa(job #2738703)

Utilizator betybety bety bety Data 6 aprilie 2021 11:28:35
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
typedef long long ll;
const ll lim=2e6+4;
const ll A=29;
const ll B=666013;
vector<ll> poz;
string a,b;
int main()
{
    in>>a>>b;
    ll ca=0,put=1;
    for(ll i=0;i<a.size();++i)
    {
        ca=(ca*A+(a[i]-'A'))%B;
        if(i) put=(put*A)%B;
    }
    ll cb=0;
    for(ll i=0;i<b.size();++i)
    {
        if(i>=a.size())
            cb=(cb+B-(put*(b[i-a.size()]-'A'))%B)%B;
        cb=(cb*A+(b[i]-'A'))%B;
        if(i<a.size()-1)
            continue;
        if(ca==cb)
            poz.push_back(i-a.size()+1);
    }
    out<<poz.size()<<'\n';
    for(ll i=0;i<min(1000LL,(ll)poz.size());++i)
        out<<poz[i]<<' ';
    return 0;
}