Cod sursa(job #3199705)

Utilizator teodor079Albert Teodor Stefan teodor079 Data 2 februarie 2024 16:02:39
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define M 1000000013
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000002],b[2000002];
unsigned long long hashA,hashB,p=1,nr,i;
void hashh();
vector<int> v;
int main()
{
    f>>a>>b;
    hashh();
    int n=strlen(a),m=strlen(b);
    if(hashA==hashB)
    {
        nr++;
        v.push_back(0);
    }
    for(i=n;i<m;i++)
    {
        hashB=((257*(hashB+M-(b[i-n]*p)%M))%M+b[i])%M;
        if(hashA==hashB)
        {
            nr++;
            v.push_back(i-n+1);
        }
    }
    g<<nr<<'\n';
    int i=0;
    if(nr<=1000)
        for(i=0;i<nr;i++)
        g<<v[i]<<" ";
    else
        for(i=0;i<1000;i++)
        g<<v[i]<" ";
    return 0;
}
void hashh()
{
    int n=strlen(a),m=strlen(b);
    for(i=0;i<n;i++)
    {
        hashA=((257*hashA)%M+a[i])%M;
        if(i!=0)
            p=(p*257)%M;
    }
    for(i=0;i<n;i++)
    {
        hashB=((257*hashB)%M+b[i])%M;
    }
}