×

CDVA1606 - Editorial

Author: Suraj Prakash
Editorialist: Suraj Prakash

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".

513
accept rate: 33%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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