// Pour deux tableaux d'entiers de longueur N, // pour tous K de 1 à N, compter le nombre de nombres communs dans les préfixes de longueur K. // Les nombres dans le tableau peuvent se répéter, l'intersection est comptée sans tenir compte des multiplicateurs. // Un préfixe de longueur K du tableau A est les premiers K éléments du tableau A // A [1, 1] => [1], [1, 1] // B [1, 1] => [1], [1, 1] // R [1, 1] // [1, 2, 5] => [1], [1, 2], [1, 2, 5] // [1, 5, 4] => [1], [1, 5], [1, 5, 4] // [1, 1, 2]

Задача: для каждого K от 1 до N посчитать количество общих уникальных чисел в префиксах длины K двух массивов.

Идея решения:

• Использовать два множества для хранения уникальных элементов префиксов каждого массива.
• Итерироваться по индексам от 0 до N-1, добавляя элементы в соответствующие множества.
• На каждом шаге считать пересечение множеств и записывать размер пересечения.

Пример на Go:

package main

import (
	"fmt"
)

func commonPrefixCounts(A, B []int) []int {
	N := len(A)
	setA := make(map[int]struct{})
	setB := make(map[int]struct{})
	result := make([]int, N)

	for i := 0; i < N; i++ {
		setA[A[i]] = struct{}{}
		setB[B[i]] = struct{}{}

		count := 0
		for val := range setA {
			if _, exists := setB[val]; exists {
				count++
			}
		}
		result[i] = count
	}
	return result
}

func main() {
	A := []int{1, 2, 5}
	B := []int{1, 5, 4}
	res := commonPrefixCounts(A, B)
	fmt.Println(res) // Output: [1 2 2]
}

Такой подход работает за O(N*M), где M — среднее количество уникальных элементов в префиксах. Для оптимизации можно использовать структуры данных с подсчетом частот и динамическим обновлением пересечения.