Your task is to search for a palindrome string of length $($n$)$ in a two$-$dimensional matrix of random single characters between a$-$z$,$ the idea of the solution is to parallelize the search between all possible threads and count each occurrence. The matrix size is $1000$x$1000,$ you can input the number you want to search or hard code it$,$ search right to left, up to down and diagonally up to down.

Make sure to include timing to your code, you need to test using different thread count for your search, you need to submit two solutions using MPI and OpenMP:

$1.$ OpenMP C file and results of execution.

$2.$ Repeat part $1$ using MPI C file and results of execution.

Code below can be used to generate the matrix:

for$($i $=0$;i $<$ ROWS;i$++)$

for$($j $=0$;j $<$ COLUMNS;j$++)$

a$[$i$][$j$]=($rand$()\%26)+\text{'}$A$\text{'}$;

Hint: start your testing with a small matrix, $10$x$10$ to make sure it is working, then scale up to $1000$x$1000.$

You can use a function for the search or string libraries.

Example of execution output:

$115038$ palindromes of size $3$ found in $0\mathrm{.}002427$ s$.$ using $1$ threads.

$4374$ palindromes of size $4$ found in $0\mathrm{.}002508$ s$.$ using $1$ threads.

$4275$ palindromes of size $5$ found in $0\mathrm{.}003136$ s$.$ using $1$ threads.

$178$ palindromes of size $6$ found in $0\mathrm{.}002827$ s$.$ using $1$ threads.

$********************************************************************************$

$115038$ palindromes of size $3$ found in $0\mathrm{.}002453$ s$.$ using $2$ threads.

$4374$ palindromes of size $4$ found in $0\mathrm{.}002186$ s$.$ using $2$ threads.

$4275$ palindromes of size $5$ found in $0\mathrm{.}002031$ s$.$ using $2$ threads.

$178$ palindromes of size $6$ found in $0\mathrm{.}002065$ s$.$ using $2$ threads.

$**$

$115038$ palindromes of size $3$ found in $0\mathrm{.}002009$ s$.$ using $3$ threads.

$4374$ palindromes of size $4$ found in $0\mathrm{.}002038$ s$.$ using $3$ threads.

$4275$ palindromes of size $5$ found in $0\mathrm{.}002102$ s$.$ using $3$ threads.

$178$ palindromes of size $6$ found in $0\mathrm{.}002114$ s$.$ using $3$ threads.

$********************************************************************************$

$115038$ palindromes of size $3$ found in $0\mathrm{.}002232$ s$.$ using $4$ threads.

$4374$ palindromes of size $4$ found in $0\mathrm{.}001983$ s$.$ using $4$ threads.

$4275$ palindromes of size $5$ found in $0\mathrm{.}001983$ s$.$ using $4$ threads.

$178$ palindromes of size $6$ found in $0\mathrm{.}002092$ s$.$ using $4$ threads.

$********************************************************************************$

$115038$ palindromes of size $3$ found in $0\mathrm{.}002146$ s$.$ using $5$ threads.

$4374$ palindromes of size $4$ found in $0\mathrm{.}001881$ s$.$ using $5$ threads.

$4275$ palindromes of size $5$ found in $0\mathrm{.}001787$ s$.$ using $5$ threads.

$178$ palindromes of size $6$ found in $0\mathrm{.}003253$ s$.$ using $5$ threads.

$*$

$115038$ palindromes of size $3$ found in $0\mathrm{.}002279$ s$.$ using $6$ threads.

$4374$ palindromes of size $4$ found in $0\mathrm{.}001906$ s$.$ using $6$ threads.

$4275$ palindromes of size $5$ found in $0\mathrm{.}001828$ s$.$ using $6$ threads.

$178$ palindromes of size $6$ found in $0\mathrm{.}001847$ s$.$ using $6$ threads.

$**$

$115038$ palindromes of size $3$ found in $0\mathrm{.}001969$ s$.$ using $7$ threads.

$4374$ palindromes of size $4$ found in $0\mathrm{.}001974$ s$.$ using $7$ threads.

$4275$ palindromes of size $5$ found in $0\mathrm{.}001799$ s$.$ using $7$ threads.

$178$ palindromes of size $6$ found in $0\mathrm{.}002704$ s$.$ using $7$ threads.

$*$

$115038$ palindromes of size $3$ found in $0\mathrm{.}002787$ s$.$ using $8$ threads.

$4374$ palindromes of size $4$ found in $0\mathrm{.}009502$ s$.$ using $8$ threads.

$4275$ palindromes of size $5$ found in $0\mathrm{.}003185$ s$.$ using $8$ threads.

$178$ palindromes of size $6$ found in $0\mathrm{.}003204$ s$.$ using $8$ threads