当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5069:Harry And Biological Teacher

题目描述
As we all know, Harry Porter learns magic at Hogwarts School. However, learning magical knowledge alone is insufficient to become a great magician. Sometimes, Harry also has to gain knowledge from other certain subjects, such as language, mathematics, English, and even algorithm.
Today, Harry is on his biological class, his teacher is doing experiment with DNA right now. But the clever teacher faces a difficult problem. He has lots of genes. Every time he picks gene a and gene b. If he want to connect gene a and gene b, he should calculate the length of longest part that the gene a’s suffix and gene b’s prefix can overlap together. For example gene a is "AAT" and gene b is "ATT", then the longest common part is "AT", so the answer is 2. And can you solve this difficult problem for him?
输入解释
They are sever test cases, you should process to the end of file.
For each test case, there are two integers n and m ($1 \leq n \leq 100000, 1 \leq m \leq 100000$)on the first line, indicate the number of genes and the number of queries.
The next following n line, each line contains a non-empty string composed by characters 'A' , 'T' , 'C' , 'G'. The sum of all the characters is less than 100000.
Then the next following m line, each line contains two integers a and b($1 \leq a, b \leq n$), indicate the query.
输出解释
For each query, you should output one line that contains an integer indicate the length of longest part that the gene a’s suffix and gene b’s prefix can overlap together.
输入样例
2 1
ACCGT
TTT
1 2
4 4
AAATTT
TTTCCC
CCCGGG
GGGAAA
1 2
2 3
3 4
4 1
输出样例
1
3
3
3
3
来自杭电HDUOJ的附加信息
Recommend heyang

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 BestCoder Round #14

源链接: HDU-5069

最后修改于 2020-10-25T23:19:26+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 32768/32768K(Java/Others)