can you help me with the followin task$($ID number $200192232)$:

Implement the KMP or BM string pattern matching algorithm. If your ID number is odd $$ implement

KMP$,$ otherwise $($if even$)$ implement BM$.$

Driver Program:

Modify the classes$$ code $($if needed$)$ and write a program to show the items that contain a certain

search string $($entered by the user$)$ in their name. Your code should traverse only the Items collection that

contains pointers to objects of both Artifact and Service classes.

After using the above algorithm to find which items contain the string, display their names and GUID,

ordered by the number of occurrences of the string, from high to low.

Here is the code you have to use:

#include

#include

#include

#include

enum DiscountTypeEnum $\{$ AMOUNT, PERCENTAGE $\}$;

class Item $\{$

public:

virtual double GetTotalPrice$()$ const $=0$;

virtual std::string GetName$()$ const $=0$;

virtual std::string GetCategory$()$ const $=0$;

virtual ~Item$()=$ default;

$\}$;

class Division $\{$

public:

std::string GUID;

std::string Name;

std::string PhoneNumber;

std::string Description;

Division$*$ Parent;

Division$($std::string guid, std::string name, std::string phone, std::string desc, Division$*$ parent$)$

: GUID$($guid$),$ Name$($name$),$ PhoneNumber$($phone$),$ Description$($desc$),$ Parent$($parent$)\{\}$

$\}$;

class Artifact : public Item $\{$

public:

std::string GUID;

std::string Name;

std::string Description;

std::string Category;

Division$*$ DivisionPtr;

double Price;

double Discount;

DiscountTypeEnum DiscountType;

int Quantity;

Artifact$($std::string guid, std::string name, std::string desc, std::string category,

Division$*$ division, double price, double discount, DiscountTypeEnum discountType, int quantity$)$

: Item$(),$ GUID$($guid$),$ Name$($name$),$ Description$($desc$),$ Category$($category$),$

DivisionPtr$($division$),$ Price$($price$),$ Discount$($discount$),$ DiscountType$($discountType$),$ Quantity$($quantity$)\{\}$

double GetEffectivePrice$()$ const $\{$

if $($DiscountType $==$ AMOUNT$)$

return std::max$(0\mathrm{.}0,$ Price $-$ Discount$)$;

else

return std::max$(0\mathrm{.}0,$ Price $-($Price $*$ Discount $/100\mathrm{.}0))$;

$\}$

double GetTotalPrice$()$ const override $\{$

return Quantity $*$ GetEffectivePrice$()$;

$\}$

std::string GetName$()$ const override $\{$

return Name;

$\}$

std::string GetCategory$()$ const override $\{$

return Category;

$\}$

$\}$;

class Service : public Item $\{$

public:

double Duration;

double Rate;

double RateDiscount;

DiscountTypeEnum RateDiscountType;

Service$($std::string guid, std::string name, std::string desc, std::string category, Division$*$ division,

double duration, double rate, double rateDiscount, DiscountTypeEnum rateDiscountType$)$

: Item$(),$ Duration$($duration$),$ Rate$($rate$),$ RateDiscount$($rateDiscount$),$ RateDiscountType$($rateDiscountType$)\{\}$

double GetEffectiveRate$()$ const $\{$

if $($RateDiscountType $==$ AMOUNT$)$

return std::max$(0\mathrm{.}0,$ Rate $-$ RateDiscount$)$;

else

return std::max$(0\mathrm{.}0,$ Rate $-($Rate $*$ RateDiscount $/100\mathrm{.}0))$;

$\}$

double GetTotalPrice$()$ const override $\{$

return Duration $*$ GetEffectiveRate$()$;

$\}$

std::string GetName$()$ const override $\{$

return "Service";

$\}$

std::string GetCategory$()$ const override $\{$

return "Service";

$\}$

$\}$;

void Merge$($std::vector& items, int left, int mid, int right$)\{$

int n$1=$ mid $-$ left $+1$;

int n$2=$ right $-$ mid;

std::vector L$($n$1),$ R$($n$2)$;

for $($int i $=0$; i $<$ n$1$; i$++)$

L$[$i$]=$ items$[$left $+$ i$]$;

for $($int j $=0$; j $<$ n$2$; j$++)$

R$[$j$]=$ items$[$mid $+1+$ j$]$;

int i $=0$; $//$ Initial index of first subarray

int j $=0$; $//$ Initial index of second subarray

int k $=$ left; $//$ Initial index of merged subarray

while $($i $<$ n$1$ && j $<$ n$2)\{$

if $($L$[$i$]->$GetTotalPrice$()<=$ R$[$j$]->$GetTotalPrice$())\{$

items$[$k$]=$ L$[$i$]$;

i$++$;

$\}$ else $\{$

items$[$k$]=$ R$[$j$]$;

j$++$;

$\}$

k$++$;

$\}$

while $($i $<$ n$1)\{$

items$[$k$]=$ L$[$i$]$;

i$++$;

k$++$;

$\}$

while $($j $<$ n$2)\{$

items$[$k$]=$ R$[$j$]$;

j$++$;

k$++$;

$\}$

$\}$

void Mergesort$($std::vector& items, int left, int right$)\{$

if $($left $>=$ right$)\{$

return; $//$ Returns recursively

$\}$

int mid $=$ left $+($right $-$ left$)/2$;

Mergesort$($items$,$ left, mid$)$;

Mergesort$($items$,$ mid $+1,$ right$)$;

Merge$($items$,$ left, mid, right$)$;

$\}$

int main$()\{$

std::vector items;

$//$ Adding items to the vector

items.push$\_$back$($new Artifact$("$ART$1",$ "Laptop", "High$-$performance laptop", "Electronics", nullptr, $185\mathrm{.}99,30,$ PERCENTAGE, $5))$;

items.push$\_$back$($new Artifact$("$ART$2",$ "Smartphone", "Latest model smartphone", "Electronics", nullptr, $999\mathrm{.}99,50,$ AMOUNT, $3))$;

items.push$\_$back$($new A