Cod sursa(job #3199708)

Utilizator Cezar1432Dogaru Cezar Cezar1432 Data 2 februarie 2024 16:05:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define P 257
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000000],b[2000000];
long long p[2000000],hasha[2000000],hashb[2000000],n,m,sol[2000000],cnt;
int k;
inline void putere()
{
    p[0]=1;
    int t=max(n,m);
    for(int i=1;i<=t;i++)
        p[i]=p[i-1]*257;
}
inline void hashh()
{
    n=strlen(a),m=strlen(b);
    putere();

    hasha[0]=hashb[0]=0;
    for(int i=1;i<=n;i++)
    {
        hasha[i]=hasha[i-1]*P+a[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        hashb[i]=hashb[i-1]*P+b[i-1];
    }
}
int main()
{
f.getline(a,2000000);
f.getline(b,2000000);
hashh();
    for(int i=0;i<m-n+1;i++)
{
    int j=i+n-1;
    if(hashb[j+1]-hashb[i]*p[n]==hasha[n])
    {
        cnt++;
        sol[++k]=i;
    }
}
g<<cnt<<'\n';
for(int i=1;i<=min(1000,k);i++)
    g<<sol[i]<<" ";



    return 0;
}