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.