Cod sursa(job #3359166)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 25 iunie 2026 16:48:18
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <cstring>
#include <ios>
#include<vector>
#include<algorithm>
using namespace std;

const int NMAX = 2e6 + 10;
const char DELIMITATOR = '#';

void compute_strings_z(char a[], char b[]) {
    strcat(a, "#");
    strcat(a, b);
}


void compute_z(char a[], int z[]) {
    int l, r;
    int n = strlen(a);
    l = r = 0;
    z[0] = 0;
    for (int i = 1; i < n; i++) {
        if (l <= i && i <= r) z[i] = z[i - l];
        else z[i] = 0;
        while ((i + z[i]) < n && a[z[i]] == a[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
}
char a[NMAX], b[NMAX];
int z[NMAX]; // z[i] = cel mai lung prefix comun intre sufixul de la pozitia 0 si sufixul la pozitia i

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s", a);
    scanf("%s", b);


    compute_strings_z(a, b);
    compute_z(a, z);


    int n = strlen(a);
    int m = n - strlen(b) - 1;

    vector<int> solutions;

    for (int i = m + 1; i < n; i++) {
        if (z[i] >= m)
            solutions.push_back(i - m - 1);
    }
    printf("%d\n", solutions.size());
    int to_print = min((int)solutions.size(), 1000);
    for (int i = 0; i < to_print; i++)
        printf("%d ", solutions[i]);
    return 0;
}