String Test

Prompt

# String Test Given two strings \(a\) and \(b\), support the following four operations: 1. Set the \(y\)th character of \(a\) to \(z\) and then output \(F(a,b)\). 2. Consider the 1-indexed substring of \(a\) starting at index \(y\) ending at index \(z\), call it \(s\). Print \(F(s,b)\). 3. Consider the suffixes of \(b\) starting with the \(y\)th and \(z\)th indexed characters, call them \(t\) and \(u\). Print \(f(t,u)\). 4. Consider the 1-indexed substrings of \(b\) starting and ending at \(l_1\) and \(r_1\), and \(l_2\) and \(r_2\). Determine if their concatenation is a substring of \(b\). Print `yes` if so, print `no` otherwise. \(f(x,y)\) is the length of the longest common prefix of \(x\) and \(y\). \(F(x,y)\) is a pair \((p,q)\) where \(p\) is the maximum value of \(f(z,y)\) where \(z\) varies over all suffixes of \(x\), and \(q\) is the number of suffixes that yield that maximum value. ## Constraints \(N, M, Q \le 10^5\) Each character in the string will be a positive integer no larger than \(10^5\). ## Input The first line contains a single integer, the test case number. You may ignore this line. The next line contains a single positive integer, \(N\), representing the length of \(a\). The next line contains \(N\) space-separated integers, the string \(a\). The next line contains a single positive integer, \(M\), representing the length of \(b\). The next line contains \(M\) space-separated integers, the string \(b\). The next line contains a single positive integer, \(Q\), representing the number of operations. The next \(Q\) lines indicate the operations to be performed in order. If the operation is the first one, there will be three space-separated integers, \(1\), \(y\), and \(z\). If the operation is the second one, there will be three space-separated integers, \(2\), \(y\), and \(z\). If the operation is the third one, there will be three space-separated integers, \(3\), \(y\), and \(z\). If the operation is the fourth one, there will be five space-separated integers, \(4\), \(l_1\), \(r_1\), \(l_2\), and \(r_2\). ## Output Print an answer for each operation. All answers go on their own lines. ## Sample Input ```text 0 10 1 2 3 3 3 1 2 3 2 1 3 1 3 1 10 3 1 3 4 3 3 2 2 2 2 10 1 3 2 2 7 9 2 7 10 2 3 9 2 2 8 1 7 1 1 4 2 ``` ## Sample Output ```text 1 yes 1 2 1 3 0 3 1 1 1 1 1 1 2 1 2 1 ``` ## Time Limit 1.0 seconds ## Memory Limit 256 MB ## Solution Requirements Write a complete solution to this problem. You may use **any programming language**, but **C++ is recommended**. Do not stop at an outline, partial implementation, pseudocode, or explanation. **Keep reasoning, writing, compiling, running, debugging, and testing until the full working solution is written and validated.** The final response must contain: 1. A complete explanation of the algorithm and why it is correct. 2. A complete implementation. 3. Complexity analysis. 4. Testing of the implementation, including the provided sample and additional edge cases. 5. Any necessary debugging or corrections discovered during testing. The solution must satisfy all stated constraints and the **1.0 seconds time limit** and **256 MB memory limit**.