Cod sursa(job #3041828)

Utilizator DariusM17Murgoci Darius DariusM17 Data 1 aprilie 2023 21:46:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
const int B1=27,B2=29,MOD1=10007,MOD2=666013 ;
string a,b ;
vector <int> pos ;
int main()
{
    fin>>a>>b ;
    int p1=1,p2=1,v1=0,v2=0,h1=0,h2=0 ;
    for(int i=0; i<a.size(); ++i)
    {
        v1=(v1*B1+a[i])%MOD1 ;
        v2=(v2*B2+a[i])%MOD2 ;
        if(i!=0) p1=(p1*B1)%MOD1,p2=(p2*B2)%MOD2 ;
    }
    for(int i=0; i<a.size(); ++i)
    {
        h1=(h1*B1+b[i])%MOD1 ;
        h2=(h2*B2+b[i])%MOD2 ;
    }
    if(v1==h1 && h2==v2) pos.push_back(0) ;
    for(int i=a.size(); i<b.size(); ++i)
    {
        h1=((h1-(b[i-a.size()]*p1)%MOD1+MOD1)*B1+b[i])%MOD1 ;
        h2=((h2-(b[i-a.size()]*p2)%MOD2+MOD2)*B2+b[i])%MOD2 ;
        if(h1==v1 && h2==v2) pos.push_back(i-a.size()+1) ;
    }
    fout<<pos.size()<<'\n' ;
    for(int i=0;i<min((int)pos.size(),1000);++i) fout<<pos[i]<<" " ;
    return 0 ;
}