You are not logged in. Please login at www.codechef.com to post your questions!

×

Pairs of Strings Editorial (CRANPAIR) - Cranium 2015

PROBLEM LINK

Contest

DIFFICULTY

Easy

SOLUTION

The naive approach to calculate the match counts for each string would result in a O(K*N^2) solution which would time out. By changing the order in which we process the strings, we can bring the runtime down to O(N^2).

We calculate the match counts in a rolling fashion. For example, for the strings abcbd, bcbad, and k = 3 we proceed as follows:
abc, bcb = 0 bcb, cba = 0 - (a == b) + (b == a) = 0 cbd, bad = 0 - (b == c) + (d == d) = 1
Thus we can get the next pair of strings' match count by subtracting the first and adding last character's count. One such pass takes O(N) time and we need to make two passes of complexity O(N^2) to get all the substrings. The string pair's position in the calculation is left as an exercise.

SETTER'S SOLUTION

Link

This question is marked "community wiki".

asked 15 Feb '15, 01:09

sanchit_h's gravatar image

6★sanchit_h
24617
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,875
×3,828
×355
×7
×1

question asked: 15 Feb '15, 01:09

question was seen: 705 times

last updated: 15 Feb '15, 01:09