b*******d
发帖数: 750 | 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] | d******b
发帖数: 73 | | b*******d
发帖数: 750 | 3
yes, I did some tricks but still several big tests can't pass.
【在 d******b 的大作中提到】
: 解决这个问题不难，难的是一个高效的算法。
| d*******l
发帖数: 338 | | b***e
发帖数: 1419 | 5 对于每一个V和P，求V和reverse(V)的KMP。然后用KMP(V)从前向后扫一遍P，用KMP(
reverse(V))从后向前扫一遍P，几下所有partial match的起始。组后扫一遍所有
partial matches，看有没有能在一个点对上并且长度合适的。这样整个的算法是线性
的。
【在 b*******d 的大作中提到】
:
: yes, I did some tricks but still several big tests can't pass.
|
|
