UVA760 DNA Sequencing 题解

Content

给出两个小写字母组成的字符串，求两个字符串的最长公共子串，如有多个按字典序顺序输出，如没有输出 No common sequence.，每两组数据间输出一个空行，最后一组数据后不应输出空行。

数据范围：字符串长度不超过 \(300\)。

Solution

原本是奔着作为 SA 的练习题来的，结果看完题目之后，我：？？？这题目有紫题？？？

话归正题。由于本题字符串的长度只有 \(300\)，因此我们可以直接暴力提取出两个字符串里面的所有子串，然后扫过去找两个字符串的公共子串，取所有公共子串的长度的最大值，然后再回去扫，把所有长度最大的公共子串丢进一个 vector 里面直接排序就可以了。

注意这道题目的特判和毒瘤的输出格式，因为这个我 WA 了好几发。

Code

namespace Solution {

    string s, t;

    map<string, int> mp;

    iv Main() {

        int kase = 0;

        while(cin >> s >> t) {

            mp.clear(), kase++;

            if(kase > 1) puts("");

            int lens = s.size(), lent = t.size(), ans = 0;

            F(int, len, 1, lens) F(int, i, 0, lens - len) mp[s.substr(i, len)] |= 1;

            F(int, len, 1, lent) F(int, i, 0, lent - len) mp[t.substr(i, len)] |= 2;

            for(auto x : mp) if(x.se == 3) ans = max(ans, (int)x.fi.size());

            if(!ans) puts("No common sequence.");

            else {

                vector<string> res;

                for(auto x : mp) if((int)x.fi.size() == ans && x.se == 3) res.push_back(x.fi);

                sort(res.begin(), res.end());

                F(int, i, 0, (int)res.size() - 1) cout << res[i] << endl;

            }

        }

        return;

    }

}

巴特西

UVA760 DNA Sequencing 题解

Content

Solution

Code

最新文章

热门文章