Cod sursa(job #3199732)

Utilizator BalanelBalan Stefan Balanel Data 2 februarie 2024 16:20:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
vector<ll> v;
ll p1=1,p2=1;
int main()
{in>>a>>b;
if(a.size()>b.size()) {
        out<<0;
        return 0;
        }
ll h1=a[0],h2=a[0];
for(ll i=1;i<a.size();i++) {
    h1=h1*31+a[i],h2=h2*37+a[i];
    p1=p1*31,p2=p2*37;
    }
ll H1=0,H2=0;
for(ll i=0;i<a.size();i++)
    H1=H1*31+b[i],H2=H2*37+b[i];
if(h1==H1 && h2==H2) v.push_back(0);
for(ll i=a.size();i<b.size();i++) {
    H1=(H1-b[i-a.size()]*p1)*31+b[i];
    H2=(H2-b[i-a.size()]*p2)*37+b[i];
    if(h1==H1 && h2==H2) v.push_back(i-a.size()+1);
    }
out<<v.size()<<'\n';
for(ll i=0;i<v.size() && i<1000;i++)
    out<<v[i]<<' ';
return 0;
}