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

×

CDVA1606 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Suraj Prakash
Tester: Aditya Kumar
Editorialist: Suraj Prakash

DIFFICULTY:

Easy

PREREQUISITES:

String Matching, KMP, Z Algorithm

PROBLEM

Given a string of length m, find the occurence of first k characters of this string in a given text of length n.

Quick Explanation:

Inbuilt STL can be used to count the number of occurrence of the first k length string of the troops he takes with him. To get this task conviently done, we need to apply KMP string matching algorithm.

Explanation:

To solve the problem we need to find the first k length string of the troop he need to win the battle. Now, this k length troop is the which will kill the troops of the opposite clan. From the given clan troop of size n, he needs to find the match of k length troop which can be efficiently done in linear time using KMP. First we need to create the KMP table for the pattern to match. Then, we have to match the k length troops using the KMP table for the given text which can be done in linear time.

OPTIMAL COMPLEXITY:

$\mathcal{O}(K + N)$

AUTHOR'S SOLUTION:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 30 Mar '16, 00:21

suraj_ch77's gravatar image

5★suraj_ch77
513
accept rate: 33%

edited 30 Mar '16, 14:50

admin's gravatar image

0★admin ♦♦
19.8k350498541

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,679
×643
×278
×70
×41
×34
×4

question asked: 30 Mar '16, 00:21

question was seen: 929 times

last updated: 30 Mar '16, 14:50