Find and Replace using Boyer-Moore Algorithm

In this problem, you are required to implement a string replacement function using the Boyer-Moore string search algorithm. Given a text, a pattern, and a replacement string, your task is to locate all non-overlapping occurrences of the pattern in the text using the Boyer-Moore algorithm and replace them with the replacement string.

Note that if the pattern is empty or is not found in the text, the original text should be returned without any modifications.

Recall that the Boyer-Moore algorithm preprocesses the pattern to generate a bad character shift table, which allows the algorithm to skip sections of the text, thus improving the efficiency of the search. For example, if the pattern has length (m) then the table is generated based on the formula: (shift(c) = m - 1 - i) for each character (c) at position (i) in the pattern (for (0 \le i < m-1)).

inputFormat

The input consists of three lines read from standard input (stdin):
1. The first line is the text string in which the search and replacement will occur.
2. The second line is the pattern to search for in the text.
3. The third line is the replacement string that will replace each occurrence of the pattern.

outputFormat

The output is a single line printed to standard output (stdout) representing the modified text after all non-overlapping occurrences of the pattern have been replaced with the replacement string.## sample

hello world, hello universe
hello
hi

hi world, hi universe