Cod sursa(job #3176880)

Utilizator paull122Paul Ion paull122 Data 27 noiembrie 2023 22:45:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
#define MOD 666013
#define VMAX 200000
#define HASH_BASE 128
#define HASH_SIZE 666013
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");



int pwr(int a,int b)
{
    if(b==0)return 1;
    int p = pwr(a,b/2)%HASH_SIZE;
    if(b%2)return p*p*a%HASH_SIZE;
    return p*p%HASH_SIZE;

}

int gethash(char *s,int len)
{
    int hval=0;
    for(int i=0;i<len;i++)
    {
        hval = (hval * HASH_BASE + s[i])%HASH_SIZE;
    }
    return hval;
}

bool cmp(char *a , char *b)
{
    int i=0;
    while(i<strlen(a) && a[i]==b[i])
    {
        i++;
    }
    return i==strlen(a);
}

int addhash(int val,char c)
{
    val = (val * HASH_BASE + c)%HASH_SIZE;
    return val;
}
int removehash(int val,char c,int put)
{
    val -= c*put %HASH_SIZE;
    if(val < 0)
    {
        val += HASH_SIZE;
    }
    return val;
}
char a[1000001];
char b[1000001];
int main()
{
    fin >> a >> b;
    vector<int> r;
    int len = strlen(a);
    int put=1;
    for(int i=1;i<=len-1;i++)put = (put * HASH_BASE ) % HASH_SIZE;

    int pathash = gethash(a,len);

    int currhash = gethash(b,len-1);
    for(int i=len-1;i<strlen(b);i++)
    {
        currhash = addhash(currhash,b[i]);
        if(currhash==pathash && cmp(a,b+i-len+1))
        {
            r.push_back(i-len+1);
        }
        currhash = removehash(currhash,b[i-len+1],put);
    }
    fout << r.size() << "\n";
    for(int i : r)
    {
        fout << i << " ";
    }
}