Please use Ubuntu, Linux, and Virtual Box to solve the problem below (this is an operating systems question):

Given two character strings s1 and s2. Write a Pthread program to find out the number of substrings, in string s1, that is exactly the same as s2.

For example, suppose number_substring(s1, s2) implements the function, then number_substring(abcdab, ab) = 2, number_substring(aaa, a) = 3, number_substring(abac, bc) = 0.

The size of s1 and s2 (n1 and n2) as well as their data are input by users. Assume that n1 mod NUM_THREADS = 0 and n2 < n1/NUM_THREADS.

The following is a sequential solution of the problem. read_f() reads the two strings from a file named string.txt and num_substring() calculates the number of substrings.

#include #include #include

#define MAX 10240

int total = 0; int n1,n2; char *s1,*s2; FILE *fp;

int readf(FILE *fp) { if((fp=fopen("strings.txt", "r"))==NULL){ printf("ERROR: can't open string.txt! "); return 0; } s1=(char *)malloc(sizeof(char)*MAX); if(s1==NULL){ printf("ERROR: Out of memory! "); return -1; } s2=(char *)malloc(sizeof(char)*MAX); if(s2==NULL){ printf("ERROR: Out of memory "); return -1; } /*read s1 s2 from the file*/ s1=fgets(s1, MAX, fp); s2=fgets(s2, MAX, fp); n1=strlen(s1); /*length of s1*/ n2=strlen(s2)-1; /*length of s2*/

if(s1==NULL || s2==NULL || n1

int num_substring(void) { int i,j,k; int count;

for (i = 0; i <= (n1-n2); i++){ count=0; for(j = i,k = 0; k < n2; j++,k++){ /*search for the next string of size of n2*/ if (*(s1+j)!=*(s2+k)){ break; }else{ count++; }

if(count==n2){ total++; /*find a substring in this step*/ } } } return total; }

int main(int argc, char *argv[]) { int count; readf(fp); count = num_substring(); printf("The number of substrings is: %d ", count); return 1; }

To compile the program with Pthread, use: $ gcc project-pthread.c -o project-pthread.o -pthread

Download the string.txt: This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. This is an apple. That is a pear. That is an orange. That is a kiwi fruit. This is an avocado. There is a peach on the tree. This is a banana. That is a berry. That is cherry. That is a haw. This is a lemon. There is a hickory on the tree. is

Write a parallel program using Pthread based on this sequential solution. Please set the thread number as 10 in your code. You can start with this template code:

#include #include #include #include

#define MAX 10240 #define NUM_THREADS 10

int n1,n2; char *s1,*s2; FILE *fp; int countArray[NUM_THREADS]={0};

//read input file and generate string s1/s2 and length n1/n2 int readf(FILE *fp) { if((fp=fopen("strings.txt", "r"))==NULL){ printf("ERROR: can't open string.txt! "); return 0; } s1=(char *)malloc(sizeof(char)*MAX); if(s1==NULL){ printf("ERROR: Out of memory! "); return -1; } s2=(char *)malloc(sizeof(char)*MAX); if(s1==NULL){ printf("ERROR: Out of memory "); return -1; } /*read s1 s2 from the file*/ s1=fgets(s1, MAX, fp); s2=fgets(s2, MAX, fp); n1=strlen(s1); /*length of s1*/ n2=strlen(s2)-1; /*length of s2*/

if(s1==NULL || s2==NULL || n1

void num_substring(int t) { //add your logic here //1, how to distribute different parts of string s1 into different threads //2, how to sum up the total number of substring from all threads }

void *calSubStringThread(void *threadid){ long tid = (long)threadid; printf("This is thread %ld ", tid); num_substring(tid); pthread_exit(NULL); }

int main(int argc, char *argv[]) { pthread_t threads[NUM_THREADS]; int t, rc; int totalNum = 0;

readf(fp);

for(t=0; t

for(t=0; t

printf("The number of substrings is: %d ", totalNum); return 1; }

To compile the program with Pthread, use: $ gcc file.c -o file.o -pthread Here file refers to your source code name

HINT: Strings s1 and s2 are stored in a file named string.txt. String s1 is evenly partitioned for NUM_THREADS threads to concurrently search for matching with string s2. After a thread finishes its work and obtains the number of local matchings, this local number is added into a global variable showing the total number of matched substrings in string s1. Finally, this total number is printed out. Please make sure the number of substrings of parallel program is the same as the serial program.

Please show source code, output screenshot of your parallel code and a report describe your code logic. Thanks!