Cod sursa(job #3363208)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 12:44:40
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int ans[1001];
int hash_b[2000002];
const int MOD=100000007;
const int B=31;
int expo(int a,int i)
{
    if (i==0)
    {
        return 1;
    }
    else
    {
        if (i%2==0)
        {
            int rasp=expo(a,i/2);
            return (rasp*rasp)%MOD;
        }
        if (i%2==1)
        {
            return (a*expo(a,i-1))%MOD;
        }
    }
}
int main()
{
    int hash_a=0,numere=0;
    string a;
    string b;
    fin >> a >> b;
    for (int i=0;i<a.size();i++)
    {
        if (a[i]>=48 && a[i]<=57)
        {
            hash_a+=((a[i]-48+1)*expo(B,i))%MOD;
        }
        if (a[i]>=65 && a[i]<=90)
        {
            hash_a+=((a[i]-(65-57)+1)*expo(B,i))%MOD;
        }
        if (a[i]>=97 && a[i]<=122)
        {
            hash_a+=((a[i]-(122-90-(65-57))+1)*expo(B,i))%MOD;
        }
    }
    for (int i=0;i<b.size();i++)
    {
        if (a[i]>=48 && a[i]<=57)
        {
            if (i!=0)
            {
                hash_b[i]=(hash_b[i-1]+(b[i]-48+1)*expo(B,i))%MOD;
            }
        }
        if (a[i]>=65 && a[i]<=90)
        {
            if (i!=0)
            {
                hash_b[i]=(hash_b[i-1]+(b[i]-(65-57)+1)*expo(B,i))%MOD;
            }
        }
        if (a[i]>=97 && a[i]<=122)
        {
            if (i!=0)
            {
                hash_b[i]=(hash_b[i-1]+(b[i]-(122-90-(65-57))+1)*expo(B,i))%MOD;
            }
        }
    }
    for (int i=0;i+a.size()-1<b.size() && numere<=1000;i++)
    {
        if (i==0)
        {
            if (hash_b[i+a.size()-1]/expo(B,i)==hash_a)
            {
                numere++;
                ans[numere]=i;
            }
        }
        else
        {
            if ((hash_b[i+a.size()-1]-hash_b[i-1])/expo(B,i)==hash_a)
            {
                numere++;
                ans[numere]=i;
            }
        }
    }
    fout << numere << '\n';
    for (int i=1;i<=numere;i++)
    {
        fout << ans[i] << ' ';
    }
    return 0;
}