Last Updated: 1 Oct, 2021
Virus Detection
Moderate
Asked in companies
In a database, each stored file is named by a string of size ‘N’. But due to some error in the security, some of the files got infected by a virus. Given two strings ‘A’ and ‘B’ and a virus string ‘C’, Your task is to tell the number of files that are not affected by the virus. An unaffected file follows the given conditions:
The name of the file should be greater than or equal to the string ‘A’.
The name of the file should be less than or equal to string ‘B’.
The name of the file should not contain the virus string as a substring ‘C’.
Since the answer can be very large, print answer % (10^9 + 7).
For Example
If N=2 and string ‘A’ = “bc” and string ‘B’ = “bm” and virus string ‘C’ = ”g”.So the files that are not affected are “bc”, “bd”, “be”, “bf”, “bh”, “bi”, “bj”, “bk”, “bl”.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N’, denoting the length of the file’s name.
The second line contains three strings corresponding to ‘A’, ’B’ and ‘C’.
Output Format:
For each test case, print an integer corresponding to the number of unaffected files % (10^9 +7).
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 500.
length of ‘A’ and ‘B’ == N.
1 <= length of string ‘C’ <= N .
Time limit: 1 sec
Approaches
In this approach, we will declare a recursive function HELPER(‘CUR’,’ TARGET’,’ VIRUS’) that returns the number of unaffected files having a name lexicographically less than or equal to ‘TARGET’.
HELPER() function will create all possible strings and check if it’s affected or not.
We will first call HELPER() function as ‘TARGET’ as ‘B’ and store it in ‘ANS’.
Then we will update ‘ANS’ as ‘ANS’ - HELPER(“”,’ A’, ’C’).
At last, we will check if ‘A’ is affected or not and increment ‘ANS’ by 1 accordingly.
Algorithm:
- Defining function HELPER(‘CUR’, ‘TARGET’,’ VIRUS’)
- If the length of ‘CUR’ is equal to ‘TARGET, do the following:
- If ‘CUR’ is greater than ‘TARGET’:
- Return 0.
- Check if the ‘CUR’ string is virus affected or not.
- For i in range 0 to (length of ‘CUR’ - length of ‘VIRUS’ -1), do the following:
- Set j as 0.
- While j<length of ‘VIRUS’ and ‘CUR’[ i+j ]==’VIRUS’[j]:
- Set j as j+1
- If j is equal to the length of ‘VIRUS’ it implies that virus is found:
- Return 0.
- Return 1. (Found an unaffected file).
- If ‘CUR’ is greater than ‘TARGET’:
- Else:
- Set ‘ANS’ as 0.
- For ‘i’ in range 0 to 25:
- Set ‘ANS’ as ( ANS + HELPER(‘CUR’+ (‘a’ + i ),’ TARGET’,’VIRUS’) ) % (10^9 + 7).
- Return ‘ANS’.
- If the length of ‘CUR’ is equal to ‘TARGET, do the following:
- Set ‘ANS’ as HELPER(““,’B’,’C’).
- Set ‘ANS’ as ( ‘ANS’ - HELPER(“”,’A’,’C’) )% (10^9 + 7).
- Check if string ‘A’ is virus affected or not.
- Set ‘TEMP’ as 1.
- For i in range 0 to (length of ‘A’ - length of ‘C’ -1), do the following:
- Set j as 0.
- While j<length of ‘C’ and ‘A’[ i+j ]==’C’[j]:
- Set j as j+1
- If j is equal to the length of ‘C’ it implies that virus is found:
- Set temp as 0.
- Break this for loop.
- Set ‘ANS’ as ( ‘ANS’ + ‘TEMP’) % (10^9 + 7).
- Return ‘ANS’.
In this approach, we will declare a recursive function HELPER(‘i’,’j’, TARGET’, ’VIRUS’,’ TIGHT’) that will return the number of non - affected files having names less than or equal to ‘TARGET’.i is the index corresponding to current filename string,j is the index corresponding to ‘VIRUS’ string and ‘TIGHT’ is a boolean parameter that will decide either we can add character till ‘z’ or till target[i].We will try to letter to the current filename and if the i is equal to length of ‘TARGET’ we will return 1 as we formed an unaffected filename. We will also use a ‘DP’ table to memoize this solution.
Algorithm:
- Defining function HELPER(‘i’,’j’, TARGET’, ’VIRUS’,’ TIGHT’,’DP’)
- If j is equal to the length of ‘VIRUS’, a virus is detected:
- Return 0.
- If i is equal to length of ‘TARGET’,a un-affected filename is formed.
- Return 1.
- If DP[i][j][‘TIGHT’] is not equal to -1.value is precomputed:
- Return ‘DP’[i][j][‘TIGHT’].
- Set ‘ANS’ as 0.
- If ‘TIGHT’ is true:
- Set ‘LIMIT’ as ‘TARGET[i]’.
- Else:
- Set ‘LIMIT’ as ‘z’.
- For ‘c’ in range ‘a’ to ‘LIMIT’, do the following:
- If ‘VIRUS[j]’ is equal to ‘c’:
- Set ‘j2’ as j+1.
- Else:
- Set ‘j2’ as 0. (Search for the virus from start).
- Set ‘NEWTIGHT’ as ‘TIGHT’ AND ‘c==’LIMIT’.
- Set ‘ANS’ as ( ‘ANS’ + HELPER(i+1,j2,’TARGET’,’VIRUS’,’NEWTIGHT’,’DP’) ) %(10^9 +7).
- If ‘VIRUS[j]’ is equal to ‘c’:
- Set ‘DP’[i][j] as ‘ANS’.
- Return ‘ANS’.
- If j is equal to the length of ‘VIRUS’, a virus is detected:
- Initialize a ‘DP’ table of size [length of ‘A’][length of ‘VIRUS’][2] to memoize this solution.
- Set all values of ‘DP’ with -1.
- Set ‘ANS’ as HELPER(0,0,’B’,’C’, 1,’DP’).
- Set all values of ‘DP’ with -1 again.
- Set ‘ANS’ as ( ‘ANS’ - HELPER(0,0,’A’,’C’,1,’DP’))% (10^9 + 7).
- Check if string ‘A’ is virus affected or not.
- Set ‘TEMP’ as 1.
- For i in range 0 to (length of ‘A’ - length of ‘C’), do the following:
- Set j as 0.
- While j<length of ‘C’ and ‘A’[ i+j ]==’C’[j]:
- Set j as j+1
- If j is equal to the length of ‘C’ it implies that virus is found:
- Set temp as 0.
- Break this for loop.
- Set ‘ANS’ as ( ‘ANS’ + ‘TEMP’) % (10^9 + 7).
- Return ‘ANS’.
Similar problems