Cod sursa(job #3162107)

Utilizator ayannnnAyan Sorouri-Amoughin ayannnn Data 28 octombrie 2023 13:04:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int b=29;
const int mod=500009;

int hsh(char A[], int start, int stop){
    int asc=0, l=strlen(A);
    for(int i=start; i<=stop; i++)
        asc=(asc*b+A[i])%mod;
    return asc;
}

char A[2000001],B[2000001];
int v[2000001];

int main()
{
    int cnt=0;
    fin>>A>>B;
    int la=strlen(A), lb=strlen(B);
    for(int i=0; i<=lb-la; i++){
        if(hsh(A,0,la-1) == hsh(B,i,i+la-1)){
            cnt++;
            v[cnt]=i;
        }
    }
    fout<<cnt<<endl;
    for(int i=1; i<=cnt; i++)
        fout<<v[i]<<' ';
    return 0;
}