#include

#include

#include

#include

#include

using namespace std;

$//$ Function to find the length of the longest overlap where the suffix of w$1$ matches the prefix of w$2$

int find$\_$overlap$($const string& w$1,$ const string& w$2)\{$

int max$\_$overlap $=0$;

int min$\_$len $=$ min$($w$1.$size$(),$ w$2.$size$())$;

for $($int i $=1$; i $<=$ min$\_$len; i$++)\{$

if $($w$1.$substr$($w$1.$size$()-$ i$)==$ w$2.$substr$(0,$ i$))\{$

max$\_$overlap $=$ i;

$\}$

$\}$

return max$\_$overlap;

$\}$

$//$ Recursive function to perform depth$-$first search to build the best WordSnake

void dfs$($const string& current$\_$word, const vector& words, set& visited, int score,

vector& path, vector& best$\_$path, int& best$\_$score$)\{$

if $($score $>$ best$\_$score$)\{$

best$\_$score $=$ score;

best$\_$path $=$ path;

$\}$

for $($int i $=0$; i $<$ words.size$()$; $++$i$)\{$

if $($visited$.$find$($i$)==$ visited.end$())\{$

int overlap$\_$len $=$ find$\_$overlap$($current$\_$word, words$[$i$])$;

if $($overlap$\_$len $>1)\{$

visited.insert$($i$)$;

path.push$\_$back$($words$[$i$])$;

dfs$($words$[$i$],$ words, visited, score $+$ overlap$\_$len $*$ overlap$\_$len, path, best$\_$path, best$\_$score$)$;

path.pop$\_$back$()$;

visited.erase$($i$)$;

$\}$

$\}$

$\}$

$\}$

$//$ Function to build the best possible WordSnake given a list of words

pair$>$ build$\_$wordsnake$($const vector& words$)\{$

vector best$\_$path;

int best$\_$score $=0$;

for $($int i $=0$; i $<$ words.size$()$; $++$i$)\{$

set visited;

visited.insert$($i$)$;

vector path $=\{$ words$[$i$]\}$;

dfs$($words$[$i$],$ words, visited, $0,$ path, best$\_$path, best$\_$score$)$;

$\}$

return $\{$best$\_$score, best$\_$path$\}$;

$\}$

int main$()\{$

int n;

cin $>>$ n; $//$ Read the number of words

vector words$($n$)$;

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

cin $>>$ words$[$i$]$; $//$ Read the words

$\}$

$//$ Find the best WordSnake

pair$>$ result $=$ build$\_$wordsnake$($words$)$;

$//$ Output the results

cout $<<$ result.first $<<$ endl;

for $($const string& word : result.second$)\{$

cout $<<$ word $<<$ endl;

$\}$

return $0$;

$\}$

For the code above please write an anlysis report with the following instructions:

Analysis Report Structure

Analytical

Summary of analytical and empirical results.$$

Performance critical code section$($s$)$

Compress trivial code segments to better present the critical code control structure.$$ This is typically found in the main$()$ method, or one level of abstraction beneath.$$

Step count analysis of each critical section.$$

Space analysis of each critical section.

Determine overall space and time complexity.

Predict runtime performance

Empirical

Describe test plan and rational for test data sets

Graph runtime performance with trend line

Determine program limitations given $3$ second time constraint and $256$MB working space.