11577: 【原1577】阿黑的质粒

题目描述

author: 黎金宁原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1577

Description

“阿黑”是一种神奇的物种，近来生物学家对其体内的基因组成非常感兴趣。我们都知道生物细胞内存在着“质粒”，“阿黑”的细胞内也是如此。质粒是由多种基因拼接在一起组成的环状结构，基因在上面是连续相接的(不考虑没有基因的部分)。由于“阿黑”的身体结构过于简单，其质粒上的基因最多只有26种，分别用小写字母a~z来表示，但每种基因可能存在多个。生物学家在寻找一种已知序列的质粒，于是从“阿黑”体内抽取了n个质粒进行研究，将每个质粒都刚好切了一刀，变成了一条条“长链”，例如：-abhhhgllt-。生物学家想知道这n个长链中有几个对应的原质粒和已知质粒是相同的。

Hint

1.长链正着读和反着读是等效的，例如-abcd-和-dcba-是同一种质粒。 2.切的位置不同但是拼回质粒以后可能会相同，例如-abcd-和-bcda-是同一种质粒。 3.符号-是标记符，不代表基因，注意避开。 4.长度不同的质粒当然不是同一种啦。

Input Format

第1行是一个整数n，代表抽取了n个质粒。

第2行是已知质粒的序列，用长链表示。

第3~n+2行是抽取的n个质粒的长链表示，每行一条链。

Output Format

输出一个整数，代表候选质粒中有几个与给定质粒相同。

Sample Input

5
-abcdefg-
-gfedcba-
-abcd-
-defgabc-
-fedcbag-
-ababcdc-

Sample Output

Limits

对于30%的数据，质粒长度\(\in [1, 10]\), \(n\in [1,100]\)。
对于100%的数据，质粒长度\(\in [1, 100]\), \(n\in [1,1000]\)。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/16.
//
// 环装字符串匹配

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    string src;
    string srcReverse;
    string tmp;
    int size;
    int count = 0;
    cin >> n;
    cin >> src;
    src = src.substr(1, src.size() - 2);
    size = src.size();
    src += src;
    srcReverse = src;
    reverse(srcReverse.begin(), srcReverse.end());

    for (int i = 0; i < n; ++i) {
        cin >> tmp;
        tmp = tmp.substr(1, tmp.size() - 2);
        if (tmp.size() != size) continue;
        if (src.find(tmp) != string::npos || srcReverse.find(tmp) != string::npos)
            ++count;
    }
    cout << count << endl;
}

FineArtz's solution

/* 阿黑的质粒 */
#include <iostream>
#include <string>
using namespace std;

int main(){
    int n;
    cin >> n;
    string s, t;
    cin >> s;
    s.erase(s.begin());
    s.erase(s.end() - 1);
    int cnt = 0;
    while (n--){
        cin >> t;
        t.erase(t.begin());
        t.erase(t.end() - 1);
        if (t.size() != s.size()) continue;
        t += t;
        if (t.find(s) != string::npos) ++cnt;
        else{
            string p(t.rbegin(), t.rend());
            if (p.find(s) != string::npos) ++cnt;
        }
    }
    cout << cnt << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    char dest[209];
    scanf("%s", dest);
    auto dest_len = strlen(dest);
    int ans = 0;

    //字符串拼接处理
    for (int i = dest_len; i >= 1; --i) {
        dest[i + dest_len - 2] = dest[i];
    }

    for (int i = 0; i < n; ++i) {
        char temp[209];
        scanf("%s", temp);
        auto temp_len = strlen(temp);
        if (temp_len == dest_len) {
            temp[temp_len - 1] = 0;
            if (strstr(dest, temp + 1) != nullptr) {
                ++ans;
                continue;
            }
            //反转
            char reverse_temp[209] = { 0 };
            for (int i = 0; i < temp_len - 2; ++i) {
                reverse_temp[i] = temp[temp_len - i - 2];
            }
            if (strstr(dest, reverse_temp) != nullptr) {
                ++ans;
                continue;
            }
        }
    }

    cout << ans;

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int N;
    cin >> N;
    char d[200], s[200], DL, SL;
    cin >> d;
    DL = strlen(d) - 2;
    int res = 0;
    for (int i = 0; i < N; i++) {
        cin >> s;
        SL = strlen(s) - 2;
        if (SL != DL) continue;
        for (int a = 0; a < DL; a++) {
            if (s[1] == d[a + 1]) {
                bool found = true;
                for (int c = a, b = 0; b < DL;) {
                    if (s[b + 1] != d[c + 1]) {
                        found = false;
                        break;
                    }
                    c = (c + 1) % DL;
                    ++b;
                }
                if (found) {
                    ++res;
                    break;
                }
                found = true;
                for (int c = a, b = 0; b < DL;) {
                    if (s[b + 1] != d[c + 1]) {
                        found = false;
                        break;
                    }
                    c--;
                    if (c < 0) c += DL;
                    ++b;
                }
                if (found) {
                    ++res;
                    break;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}