Cod sursa(job #2862331)

Utilizator Alex_DiaconuDiaconu Alexandru Alex_Diaconu Data 5 martie 2022 11:54:01
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <string>

using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

const int mod=666133;
const int mod2=666134;
int v[2000001];
string a, b;

int main()
{
    long long a1=0, b1=0, a2=0, b2=0, r=0, h=1, h2=1, g;
    int t=1;
    cin >> a >> b;
    g='z'-'0'+2;
    for (int i=1; i<a.length(); i++)
    {
        h=(h*g)%mod;
        h2=(h2*g)%mod2;
    }
    for (int i=0; i<a.length(); i++)
    {
        a1=(a1*g+a[i]-'0')%mod;
        a2=(a2*g+a[i]-'0')%mod2;
    }
    for (int i=0; i<a.length(); i++)
    {
        b1=(b1*g+b[i]-'0')%mod;
        b2=(b2*g+b[i]-'0')%mod2;
    }
    if (b1==a1 && b2==a2)
    {
        r++;
        v[t++]=1;
    }
    for (int i=a.length(); i<b.length(); i++)
    {
        b1=((b1-h*(b[i-a.length()]-'0'))%mod+mod)%mod;
        b1=(b1*g+b[i]-'0')%mod;
        b2=((b2-h2*(b[i-a.length()]-'0'))%mod2+mod2)%mod2;
        b2=(b2*g+b[i]-'0')%mod2;
        if (b1==a1 && b2==a2)
        {
            r++;
            v[t++]=i-a.length()+1;
        }
    }
    cout << r << "\n";
    for (int i=1; i<min(t, 1000); i++)
    {
        cout << v[i] << " ";
    }
    return 0;
}