Solved–A12 –Solution

Description

Contest Link – https://www.hackerrank.com/a12-1

Problem Statement –

As you know, the world is suffering from Covid-19. Teams of scientists are currently working on developing vaccines for this deadly disease.

Chandu being a medical sciences student, is currently working on studying the history of corona viruses. He found out that viruses evolve. Each virus has a DNA sequence(which can be represented by a sequence of uppercase characters). Whenever a virus evolves, some of the DNAs in the sequence gets modified.

Chandu found out that corona viruses have a particular DNA sequence X, of lengthN. Chandu is working on a medicine Vof length M (medicine is also represented as a sequence of uppercase characters). The medicine V can be used to cure covid-19 only if the DNA sequence X of the virus contains within it the DNA sequence of the medicine and the number of such occurrences (C1) is atleast Ki.e. medicine V will cure the disease X if V is a substring of X and number of occurrences of V in X is greater than equal to K.

Also the virus X has evolved and a new virus Y has been generated. The evolution happens in the following way –

X(1…N) is the old DNA sequence. Evolution happens in Qstages. In the ith stage, each characterof the substring X(L…R) gets rotated by si characters (1<=L,R<=N). Rotation of a character c by si means shifting c by si characters towards right in the alphabet sequence (which involves looping back from ‘Z’ to ‘A’ if needed)

For Example –

1) Rotating ‘A’ by 1 gives ‘B’.

2) Rotating ‘D’ by 5 gives ‘I’.

3) Rotating ‘Y’ by 4 gives ‘C’.

4) Rotating ‘A’ by 30 gives ‘E’ and so on.

X undergoes Q such evolutions and we obtain Y. Now chandu wants to find if the same medicine V will work on the new virus Y i.e. if number of occurrences of V in Y (C2) is atleast K.
Chandu finds this task difficult. Since Chandu is your friend, you need to help him find the string Y and whether the medicine will cure X and Y.

Input Format

First line of input contains the number of test cases T.

For each test case, the first line contains the DNA sequence of the initial virus (X).

Next line contains the DNA sequence of the medicine (V).

Next line contains a single integer K.

Next line contains a single integer Q, the number of evolutions to be performed on X.

Each of the next Q lines contains three integers Li , Ri and si , such that each character of X( Li… Ri ) gets rotated by si characters(1<=i<=Q)

Output Format

For each test case, output will contain three lines.

First line contains a string YES if medicine V can cure the disease X and NO if the disease can not be cured.

Next line contains the count of occurrences of V in X (C1).

Next line contains the DNA sequence Y.

Next line contains a string YES if medicine V can cure the disease Y and NO if the disease can not be cured.

Next line contains the count of occurrences of V in Y (C2).

Constraints

1<=T<=10

1 <= N <= 10^5 (N is the length of string X)

1 <= M <= 10^5 (M is the length of string V)

1 <= Q <= 10^5

1 <= K <= 10^5 Sample Test case Input 1 – 1 ABBBCBBBBD BBB 2 2 1 1 4 8101 Output 1 – YES 3 EBBBCBBCCE NO 1 Explanation – String\Index 1 2 3 4 5 6 7 8 9 10 X A B B B C B B B B D After First E B B B C B B B B D Modification After Second E B B B C B B C C E modification(Y) X has three occurrences of substring V i.e. X(2..4), X(6..8) and X(7..9) matches V. Since 3>=2, the answer is YES.

Y has only one occurrence of substring V and hence the answer is NO.

Note – Two substrings are considered different if they have at least one non common index. Also substring X(L..R) includes both L and R also.