Multiprocessor programming problem in c?

Question

Algorithms

Hello everyone, the task is to find the longest sequence wrapped in side brackets - "<" and ">".

That is, if the character array contains sequences <a>and <bbb>, then the answer will be <bbb>.

How can this problem be solved by fork processes? Maybe there are some materials that will help with this.

Answer 1

I so understood, it is necessary to parallelize? Look at OpenMP - it works in C/C++. Parallelization is very easy to do - insert some directives into the code, compilation keys and everything works.
How to solve the problem in parallel: Break the whole line into N (number of threads) parts and each thread separately for each part will find the answer inside it. And also two values: The very last character '<', the very first character '<' and in general, whether they are in this piece.
Then the non-parallel part, which will choose the best answer from N pieces, and also check what is the longest answer distributed over the pieces. For this, you have everything - you know in each piece which character can be the beginning <...> going to the next pieces and which one can be the end. We must also consider the case that in a given piece the last <to the left of the first> - then the segment <...> cannot stick out of this piece. Otherwise, look where the segment can begin to the left. All this is implemented in one cycle for N iterations. It is necessary to store the last character < in the previous pieces, which is not yet closed. Either close with the current piece and compare with the answer, or cut it off (if the piece starts with <) or continue the segment into the next piece.