Cod sursa(job #3176906)

Utilizator paull122Paul Ion paull122 Data 28 noiembrie 2023 00:23:50
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
#define MOD 666013

#define P 73
#define HSIZE1 100021
#define HSIZE2 100007

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


char a[2000001];
char b[2000001];
bool ans[2000001];
int main()
{
    fin >> a >> b;
    if(strlen(a) > strlen(b))
    {
       fout << 0;
        return 0;
    }
    int m = strlen(b);
    int cnt=0;
    int put1=1,put2=1;
    int strhash1=0,strhash2=0;
    int pathash1=0,pathash2=0;
    int len = strlen(a);

    for(int i=0;i<len;i++)
    {
        pathash1 = (pathash1 * P + a[i])%HSIZE1;
        pathash2 = (pathash2 * P + a[i])%HSIZE2;
        strhash1= (strhash1 * P + b[i])%HSIZE1;
        strhash2 = (strhash2 * P + b[i])%HSIZE2;
        if(i)
        {
            put1 = put1 * P % HSIZE1;
            put2 = put2 * P % HSIZE2;
        }

    }
    if(strhash1 == pathash1 && strhash2 == pathash2)
    {
        ans[0]=1;
    }
    for(int i=len;i<m;i++)
    {
        strhash1 = ((strhash1 - (b[i-len]*put1) % HSIZE1 + HSIZE1)*P + b[i])%HSIZE1;
        strhash2 = ((strhash2 - (b[i-len]*put2) % HSIZE2 + HSIZE2)*P + b[i])%HSIZE2;
        if(strhash1 == pathash1 && strhash2 == pathash2)
        {
            ans[i-len+1]=1;
            ++cnt;
        }
    }
    fout << cnt << " ";
    int k=0;
    for(int i=0;i<m && k<1000;i++)
    {
        if(ans[i])
        {
            fout << i << " ";
            ++k;
        }
    }
}