Cod sursa(job #3268158)

Utilizator yellowGreenFatu Mihai yellowGreen Data 13 ianuarie 2025 19:52:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
using ll = long long;
const int mod=666063;
string s,p;
int n,m,val[200];
vector<int> ans;
int xlan(int x,int n)
{
    if(n==0) return 1;
    else
    {
        int p=xlan(x,n/2);
        if(n%2==0) return 1LL*p*p%mod;
        else return 1LL*p*p%mod*1LL*x%mod;
    }
}
int init_hash(int fi,int se,string s)
{
    ll ans=0;
    for(int i=fi;i<se;i++)
        ans=(ans*62+val[s[i]])%mod;
    return ans%mod;
}
void init_val()
{
    int v=-1;
    for(int i='a';i<='z';i++)
        val[i]=++v;
    for(int i='A';i<='Z';i++)
        val[i]=++v;
    for(int i='0';i<='9';i++)
        val[i]=++v;
}
bool egale(string a,string b)
{
    if(a.size()!=b.size()) return 0;
    for(int i=0;i<a.size();i++)
        if(a[i]!=b[i]) return 0;
    return 1;
}
int main()
{
    cin>>p>>s;
    n=size(s);
    m=size(p);
    init_val();
    ll q=xlan(62,m-1);
    ll hp=init_hash(0,m,p);
    ll hs=init_hash(0,m,s);
    for(int i=0;i<=n-m;i++)
    {
        if(hp==hs)
            ans.push_back(i);
        hs=hs+mod-(1LL*q*val[s[i]])%mod;
        hs=hs*62%mod+val[s[i+m]]; hs%=mod;
    }
    cout<<ans.size()<<"\n";
    for(int i=0;i<min(1000,(int)ans.size());i++)
        cout<<ans[i]<<" ";
    return 0;
}