Cod sursa(job #2190630)

Utilizator NashikAndrei Feodorov Nashik Data 31 martie 2018 13:07:23
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <cstring>
#include <fstream>
using namespace std;
long long cod(char c)
{
    return c - 'A';
}

const long long BASE = 29;
const long long MOD = 10000007;

long long powBase[2000005];

long long hashPref[2000005];
char T[2000005];
char P[2000005];

long long cod(char* s)
{
    long long answer = 0;
    while (s[0] != '\0')
    {
        answer = (answer * BASE + cod(s[0])) % MOD;
        s++; // ca si cand am 'sterge' primul caracter
    }
    return answer;
}


long long hashh(long long i, long long j)
{
    return (hashPref[j] + MOD - hashPref[i - 1] * powBase[j - (i - 1)] % MOD) % MOD;
}

//   i j
//abcdefghi
//abcdef
//abc---
int v[2000005];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",P,T);
    long long lenT=strlen(T);
    long long lenP=strlen(P);
    powBase[0]=1;
    for(long long i=1;i<=2000005;i++)
        powBase[i]=powBase[i-1]*BASE%MOD;
    hashPref[0]=(cod(T[0])+MOD)%MOD;
    for(long long i=1;i<lenT;i++)
        hashPref[i]=(hashPref[i-1]*BASE+cod(T[i]))%MOD;
    long long Phash=cod(P);
    long long cnt=0;
    for(long long i=0;i+lenP<=lenT;i++)
        if(Phash==hashh(i,i+lenP-1)){
            v[++cnt]=i;
        }
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
        printf("%d ",v[i]);
    return 0;
}