Cod sursa(job #3017128)

Utilizator tmi26Teodor Stupariu tmi26 Data 17 martie 2023 10:52:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long baza=128,mod1=1e9+3,mod2=1e9+7;
long long hash1=0,hash2=0,hashf1=0,hashf2=0,hashh1=1,hashh2=1;
long long pmod(long long a,long long b,long long mod)
{
    a*=b;
    a%=mod;
    return a;
}
long long adunare(long long a,long long b,long long mod)
{
    a+=b;
    a%=mod;
    return a;
}
long long scot(long long has,long long hashh,long long mod)
{
    has-=hashh;
    has+=mod;
    has%=mod;
    return has;
}
vector <long long> sol;
int main()
{
    string s1,s2;
    fin>>s1>>s2;
    long long n,m,cnt=0;
    n=s1.size();
    m=s2.size();
    for(long long i=0; i<n; i++)
    {
        hash1=pmod(hash1,baza,mod1);
        hash2=pmod(hash2,baza,mod2);
        hash1=adunare(hash1,(long long)s1[i],mod1);
        hash2=adunare(hash2,(long long)s1[i],mod2);
        ///
        hashf1=pmod(hashf1,baza,mod1);
        hashf2=pmod(hashf2,baza,mod2);
        hashf1=adunare(hashf1,(long long)s2[i],mod1);
        hashf2=adunare(hashf2,(long long)s2[i],mod2);
        ///
        if(i<n-1)
        {
            hashh1=pmod(hashh1,baza,mod1);
            hashh2=pmod(hashh2,baza,mod2);
        }
    }
    if(hash1==hashf1&&hash2==hashf2)
    {
        cnt++;
        sol.push_back(0);
    }
    for(long long i=n; i<m; i++)
    {
        long long st=i-n;
        hashf1=scot(hashf1,pmod(hashh1,(long long)s2[st],mod1),mod1);
        hashf2=scot(hashf2,pmod(hashh2,(long long)s2[st],mod2),mod2);
        hashf1=pmod(hashf1,baza,mod1);
        hashf2=pmod(hashf2,baza,mod2);
        hashf1=adunare(hashf1,(long long)s2[i],mod1);
        hashf2=adunare(hashf2,(long long)s2[i],mod2);
        if(hash1==hashf1&&hash2==hashf2)
        {
            cnt++;
            if(sol.size()<1000)
                sol.push_back(st+1);
        }
    }
    fout<<cnt<<'\n';
    for(auto it:sol)
        fout<<it<<" ";
    return 0;
}