Cod sursa(job #3333424)

Utilizator Rradu_v2Catana Radu Rradu_v2 Data 13 ianuarie 2026 14:32:52
Problema Potrivirea sirurilor Scor 40
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <stdio.h>

#define MAX_SECV_N 2000000
#define BAZA 91514629
#define MOD 91511197

char a[MAX_SECV_N], b[MAX_SECV_N];
unsigned long long aenc[MAX_SECV_N], benc=0;
unsigned long long BAZAlam;
int pos[1000];
unsigned long long fastexp(unsigned long long b, int p) {
    if(p==0)
        return 1;
    unsigned long long y = fastexp(b, p/2);
    y = (y*y)%MOD;
    if(p%2==1)
        y = (y*b)%MOD;
    return y;
}

int main()
{
    //FILE *fin = fopen("D:/GitHub_Repos/AlgoArchive/Algo_v2/InfoArena/PotrivireaSirurilor/strmatch.in", "r");
    //FILE *fout = fopen("D:/GitHub_Repos/AlgoArchive/Algo_v2/InfoArena/PotrivireaSirurilor/strmatch.out", "w");
    FILE *fin = fopen("strmatch.in", "r");
    FILE *fout = fopen("strmatch.out", "w");
    int n=0, m=0, i, j, p=0;
    unsigned long long xfinal, x1, x2;
    char ch, val;

    ch = fgetc(fin);
    while(ch!='\n') {
        b[m] = ch;
        m++;
        ch = fgetc(fin);
    }
    BAZAlam = fastexp(BAZA, m);

    ch = fgetc(fin);
    while(ch!=EOF && ch!='\n') {
        a[n] = ch;
        n++;
        ch = fgetc(fin);
    }

    for(i=0; i<m; i++) {
        if('a'<=b[i]&&b[i]<='z')
            val = b[i]-'a';
        else
            val = b[i]-'A'+26;
        benc = (benc*BAZA+val)%MOD;
    }

    if('a'<=a[0]&&a[0]<='z')
        aenc[0] = a[0]-'a';
    else
        aenc[0] = a[0]-'A'+26;
    for(i=1; i<n; i++) {
        if('a'<=a[i]&&a[i]<='z')
            val = a[i]-'a';
        else
            val = a[i]-'A'+26;
        aenc[i] = (aenc[i-1]*BAZA+val)%MOD;
    }

    i=0;
    while(i<=n-m) {
        x1 = aenc[i+m-1];
        if(i==0)
            x2 = 0;
        else
            x2 = (aenc[i-1]*BAZAlam)%MOD;
        xfinal = (x1-x2+MOD)%MOD;
        if(xfinal == benc) {
            j=0;
            while(j<m && b[j]==a[i+j])
                j++;
            if(j==m) {
                if(p<1000)
                    pos[p] = i;
                p++;
            }
        }

        i++;
    }

    fprintf(fout, "%d\n", p);
    for(i=0; i<p; i++)
        fprintf(fout, "%d ", pos[i]);
    fprintf(fout, "\n");

    fclose(fin);
    fclose(fout);
    return 0;
}