Show matching categories in search page

Essentially what you need is show the categories the current queried posts belong.
I’ll post here a function that take as argument a taaxonomy (or an array of taxonomies) and return all the terms in that (those) taxonomy(ies) that are assigned to all queried posts.

function queried_posts_terms( $taxonomies="category" ) {
  global $wp_query, $wpdb;
  if ( empty( $wp_query->posts ) ) return FALSE;
  $ids = wp_list_pluck( $wp_query->posts, 'ID' );
  $taxonomies = array_filter( (array) $taxonomies, function( $tax ) {
    if ( is_string( $tax ) ) {
      $tax = sanitize_title( $tax );
      return taxonomy_exists( $tax ) ? esc_sql( $tax ) : NULL;
    }
  } );
  if ( empty( $taxonomies ) ) return FALSE;
  $sql = "SELECT t.name, t.slug, t.term_group, tt.*
    FROM {$wpdb->terms} t
    INNER JOIN {$wpdb->term_taxonomy} tt ON t.term_id = tt.term_id
    INNER JOIN {$wpdb->term_relationships} tr ON tt.term_taxonomy_id = tr.term_taxonomy_id
    WHERE tr.object_id IN (" . implode( ', ', $ids ) . ")
    AND tt.taxonomy IN ('" . implode( "', '", $taxonomies ) . "')
    GROUP BY t.term_id";
  return $wpdb->get_results( $sql );
}

Once you have this function in your functions.php (or in an active plugin) in your template, propably search.php just use:

if ( is_search() ) {
  $cats = queried_posts_terms( 'category' );
  echo ! empty( $cats ) ? '<ul>' : '';
  foreach( $cats as $cat ) {
    printf( '<li><a href="https://wordpress.stackexchange.com/questions/158895/%s">%s</a></li>', get_term_link($cat), esc_html($cat->name) );
  }
  echo ! empty( $cats ) ? '</ul>' : '';
}