Kattis - virus【字符串】
题意 有一个正常的DNA序列，然后被病毒破坏。病毒可以植入一段DNA序列，这段插入DNA序列是可以删除正常DNA序列中的一个连续片段的。 简单来说就是，给你一段字符串，然后这段字符串中插入一段，删掉一段。然后可以不插入，只删除。也可以只插入，不删除。但是 插入的只有一段，删除的也只有一段。也就是说 ATAA T 这组数据 删掉两边是不对的。 而且 插入的那段和删除的那段 必须是连着的。 也就是说 ATAT TATAA 这组数据 我们应该视为 删除了ATAT 再插入 TATAA 而不应该视为 删除左边的A 在右边插入AA 。 然后题目 最后要求 插入的最小的那段字符串。
思路 先顺着扫一遍，找到第一个不相同字符的位置，再逆着扫一遍，找到 不相同字符的位置。 但是这样做有一个弊端。需要考虑很多特例。 比如 AA AAAAA
AAAAA AA
AG TGGGGGGGGGGG
AG TTTTTTTTTTTTTTTTTTG
AAABBBF AABF
其实 顺着扫的时候 就把相同的字符给erase掉 然后再逆着扫的时候 遇到相同的字符 同样给erase 掉 这样就能避免掉很多的问题。
AC代码
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<string> #include<sstream> #include<set> #include<map> #include<vector> #include<queue> #include<stack> #include<numeric> using namespace std; const int MAX = 0x3f3f3f3f; const int MIN = 0xc0c0c0c0; const int maxn = 1e5 + 5; int main() { string a, b; cin >> a >> b; int len_a = a.size(), len_b = b.size(); while(a[0] == b[0] && a.size() && b.size()) { a.erase(0, 1); b.erase(0, 1); } while(a[a.size() - 1] == b[b.size() - 1] && a.size() && b.size()) { a.erase(a.size() - 1, 1); b.erase(b.size() - 1, 1); } cout << b.size() << endl; }转载于:https://www.cnblogs.com/Dup4/p/9433405.html
相关资源：JAVA上百实例源码以及开源项目