Cod sursa(job #3206390)

Utilizator G3K0Airinei Gabriel Vlad G3K0 Data 22 februarie 2024 16:09:46
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int mod1=1e5+7;
const int mod2=1e5+21;
const int p=73;
string A;
string B;
int h1a,h2a,p1,p2;

int a,b;
vector <int > ans;
int main()
{

    f>>A;
    f>>B;
    a=A.size();
    b=B.size();
    if(a>b)
        {cout<<0;
            return 0;
        }

    p1=p2=1;
    h1a=h2a=0;
    for(int i=0; i<a; i++)
    {
        h1a=(h1a*p +A[i])%mod1;
        h2a=(h2a*p +A[i])%mod2;
        if(i)
        {
            p1=(p1*p)%mod1;
            p2=(p2*p)%mod2;
        }

    }
    int h1=0,h2=0;

    for(int i=0; i<a; i++)
    {
        h1=(h1*p +B[i])%mod1;
        h2=(h2*p +B[i])%mod2;

    }

    if(h1a==h1 && h2a==h2)
        ans.push_back(0);

    for(int i=a; i<b; i++)
    {
        h1=((h1-(B[i-a]*p1)%mod1+mod1)*p+B[i])%mod1;
        h2=((h2-(B[i-a]*p2)%mod2+mod2)*p+B[i])%mod2;
        if(h1==h1a && h2==h2a)
            ans.push_back(i-a+1);
    }
    int nr=0;
g<<ans.size()<<'\n';
    for(auto it : ans)
    {
        ++nr;
        g<<it<<' ';
        if(nr==1000)
            break;
    }

    return 0;
}