Cod sursa(job #3328559)

Utilizator vladinfo_Grecu Vlad vladinfo_ Data 9 decembrie 2025 11:55:24
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
/// Template Dutzu
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define MOD 1000000007
#define int long long
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001],b[2000001];
vector<int> v;
int expo(int a, int n)
{
    int p=1;
    while (n)
    {
        if (n%2)
            p=(1LL*p*a)%MOD;
        n/=2;
        a=(1LL*a*a)%MOD;
    }
    return p;
}
 main()
{
    fast
    fin.getline(a,2000001);
    fin.getline(b,2000001);
    int lg=strlen(a);
    long long vala=0;
    long long p=1;
    for (int i=0;i<lg;i++)
    {
        if (a[i]>='a')
            vala=(vala+(a[i]-'a')*p)%MOD;
        else
            vala=(vala+(a[i]-'A'+26)*p)%MOD;
        p=(p*54)%MOD;
    }
    p=1;
    long long valb=0;
    int lgm=strlen(b);
    if (lg>lgm)
    {
        fout<<0;
        return 0;
    }
    for (int i=0;i<lg;i++)
    {
        if (b[i]>='a')
            valb=(valb+(b[i]-'a')*p)%MOD;
        else
            valb=(valb+(b[i]-'A'+26)*p)%MOD;
        p=(p*54)%MOD;
    }
    if (vala==valb)
        v.push_back(0);
    int j=lg;
    long long inv54=expo(54,MOD-2);
    while (j<lgm)
    {
        if (b[j-lg]>='a')
            valb=(valb-(b[j-lg]-'a')+MOD)%MOD;
        else
            valb=(valb-(b[j-lg]-'A'+26)+MOD)%MOD;
        if (b[j]>='a')
            valb=(valb+(b[j]-'a')*p)%MOD;
        else
            valb=(valb+(b[j]-'A'+26)*p)%MOD;
        valb=(1LL*valb*inv54)%MOD;
        if (vala==valb)
            v.push_back(j-lg+1);
        j++;
    }
    int l=v.size();
    fout<<l<<'\n';
    for (int i=0;i<min(l,1000);i++)
        fout<<v[i]<<' ';
    return 0;
}