PTA： 字符串的模式匹配

题目

本题目要求读入两个两个DNA序列A和B，其中A为人的DNA序列，B为病毒的DNA序列，然后判断A中是否出现病毒B（注：病毒的DNA序列为环状）。

输入格式

输入一个整数n，然后输入n对DNA序列（每一DNA序列为一字符串，长度不超过10000）。

输出格式

针对每一对DNA序列A和B，若B在A中出现，则输出Yes，否则输出No

输入样例

2
AAAAAAAAACCCCGGGGTTTTTTTAGTCCCTTGGGAAATCGAAGTC 、GTCAAAAAAAAA

GGGGTTTTTCCCCCCAAAATTTCCCGGGTTTTTT 、TTTTGGGGTTT

输出样例

Yes
Yes

思路

1. IsVinDNA 函数：检查病毒DNA序列是否出现在人的DNA序列中的函数。它接受两个字符串参数 a 和 b，其中 a 代表人的DNA序列，而 b 代表病毒DNA序列。

首先，函数获取字符串 a 和 b 的长度并存储在 lena 和 lenb ，以便后续比较。

然后，检查病毒DNA序列 b 的长度是否大于人的DNA序列 a 的长度，如果是，直接返回 false（病毒DNA序列无法包含在人的DNA序列中）

接下来，创建一个字符串 cir（circle，环），将人的DNA序列 a 连接自身，实际上是构造了一个环状的DNA序列。

最后，用 find 函数查找病毒DNA序列 b 是否在环状DNA序列 cir 中出现

2. main中通过一个循环，对每一对DNA序列进行处理。在每次循环中，读取两个字符串 s1 和 s2，分别代表人的DNA序列和病毒DNA序列。然后调用 IsVinDNA 函数来检查病毒DNA序列是否出现在人的DNA序列中。最后根据检查结果，输出 “Yes” 或 “No”。

这段代码的思路是将人的DNA序列连接自身，构造成一个环状的DNA序列，然后检查病毒DNA序列是否在这个环状序列中出现

注意事项：

使用的字符串的 find 函数来检查是否包含子串（C语言可以用strstr，效果差不多）

代码

#include
#include
using namespace std;

bool IsVinDNA(const string&a,const string&b)
{
    int lena = a.length();
    int lenb = b.length();
    if(lenb > lena)
        return false;
    string cir = a+a;
    if(cir.find(b) != string::npos)
        return true;
    return false;
}
int main()
{
    int n;
    cin>>n;
    string s1,s2;
    for(int i =0 ;i<n;i++)
    {
        cin>>s1>>s2;
        if(IsVinDNA(s1,s2))
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34