Cod sursa(job #3178816)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 2 decembrie 2023 15:43:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
long long pow1=1,pow2=1;
const long long MOD1=1e9+7;
const long long MOD2=4e9+7;
const long long ct=256;
void rolhash(long long &val, char c1, char c2, long long mod, long long pow)
{
    val=((mod+val-pow*c1%mod)*ct+c2)%mod;
}
int poz[1001];
char pattern[2000001],txt[2000001];
int main()
{
    cin>>pattern>>txt;
    int n=strlen(pattern),m=strlen(txt),i;
    long long hashp1=0,hashp2=0;
    for(i=0;i<n-1;i++)
    {
        pow1=pow1*ct%MOD1;
        pow2=pow2*ct%MOD2;
        hashp1=(hashp1*ct+pattern[i])%MOD1;
        hashp2=(hashp2*ct+pattern[i])%MOD2;
    }
    hashp1=(hashp1*ct+pattern[i])%MOD1;
    hashp2=(hashp2*ct+pattern[i])%MOD2;
    long long hash1=0,hash2=0;
    int rez=0;
    for(i=0;i<n&&i<m;i++)
    {
        hash1=(hash1*ct+txt[i])%MOD1;
        hash2=(hash2*ct+txt[i])%MOD2;
    }
    i--;
    while(i<m)
    {
        if(hash1==hashp1&&hash2==hashp2)
        {
            rez++;
            poz[rez]=i-n+1;
        }
        i++;
        hash1=((MOD1+hash1-pow1*txt[i-n]%MOD1)*ct+txt[i])%MOD1;
        hash2=((MOD2+hash2-pow2*txt[i-n]%MOD2)*ct+txt[i])%MOD2;
    }
    cout<<rez<<'\n';
    rez=min(rez,1000);
    for(i=1;i<=rez;i++)
        cout<<poz[i]<<" ";
    return 0;
}