Citi Hhonors 出sears10％ offer了# Money - 海外理财
b*d
1 楼
一个公司发的。感觉不容易。
－－－－－－－－－－－－－－－－－－－－－－－－－
Save Humanity(30points)
Oh!! The mankind is in trouble again.This time its a deadly disease
spreading with rate never seen before. Efficient detectors for the virus
responsible is the need of hour. You being the lead at Central Hospital need
to find a fast and reliable way to detect the 'foot-prints' of virus DNA in
that of patient.
The DNA of patient as well as of virus consist of lower case letters. Since
the data collected is raw there might be some errors.So you need to find all
substrings in the patient DNA that exactly matches the virus DNA with
exception of one at most one mismatch.
For example tolerating at most one mismatch, "aa" and "aa" are matching, "ab
" and "aa" are matching, while "ab" and "ba" are not.
Input:
The first line contains the number of test cases T. T cases follow. Each
case contains two lines containing strings P(Patient DNA) and V(Virus DNA) .
Each case is followed by a blank line.
Output:
Output T lines, one corresponding to each case. For each case, output a
space delimited list of starting indices (0 indexed) of substrings of P
which are matching with V according to the condition mentioned above . The
indices has to be in increasing order.
Constraints:
1 <= T <= 10
P and V contain at most 100000 characters each.
All characters in P and V are lowercase letters.
Sample Input:
3
abbab
ba
hello
world
banana
nan
Sample Output:
1 2
0 2
Explanation:
For the first case, the substrings of P starting at indices 1 and 2 are "bb"
and "ba" and they are matching with the string V which is "ba".
For the second case, there are no matching substrings so the output is a
blank line.
Download sample testcases as zip ['Compile & Test' will run your code
against these testcases. Avoid using Notepad for viewing these testcases]
－－－－－－－－－－－－－－－－－－－－－－－－－
Save Humanity(30points)
Oh!! The mankind is in trouble again.This time its a deadly disease
spreading with rate never seen before. Efficient detectors for the virus
responsible is the need of hour. You being the lead at Central Hospital need
to find a fast and reliable way to detect the 'foot-prints' of virus DNA in
that of patient.
The DNA of patient as well as of virus consist of lower case letters. Since
the data collected is raw there might be some errors.So you need to find all
substrings in the patient DNA that exactly matches the virus DNA with
exception of one at most one mismatch.
For example tolerating at most one mismatch, "aa" and "aa" are matching, "ab
" and "aa" are matching, while "ab" and "ba" are not.
Input:
The first line contains the number of test cases T. T cases follow. Each
case contains two lines containing strings P(Patient DNA) and V(Virus DNA) .
Each case is followed by a blank line.
Output:
Output T lines, one corresponding to each case. For each case, output a
space delimited list of starting indices (0 indexed) of substrings of P
which are matching with V according to the condition mentioned above . The
indices has to be in increasing order.
Constraints:
1 <= T <= 10
P and V contain at most 100000 characters each.
All characters in P and V are lowercase letters.
Sample Input:
3
abbab
ba
hello
world
banana
nan
Sample Output:
1 2
0 2
Explanation:
For the first case, the substrings of P starting at indices 1 and 2 are "bb"
and "ba" and they are matching with the string V which is "ba".
For the second case, there are no matching substrings so the output is a
blank line.
Download sample testcases as zip ['Compile & Test' will run your code
against these testcases. Avoid using Notepad for viewing these testcases]
