字符串匹配+递归

解题思路

酶切本身就是一个字符串查找的过程，用酶的序列去匹配DNA序列。 注：传统的字符串查找可能导致超时，所以需要先学习KMP字符串查找

然后需要考虑对酶切后的子链进行再次酶切的问题，其中涉及到两种酶的酶切点位可能重叠，所以需要对酶切后的子链分别尝试用不同酶再次酶切，此过程使用递归实现

代码示例

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

vector<string> ans;
vector<vector<int>> nexts;
vector<string> meis;
vector<int> cutIndexs;

// 构建每个酶KMP匹配使用的next表 
vector<int> build_next(string b)
{
	vector<int> next(b.size(), 0);
	int k = 0;
	for (int i = 1; i < b.size(); i++)
	{
		while(k > 0 && b[i] != b[k])
		{
			k = next[k - 1];
		}
		
		if (b[i] == b[k])
		{
			k++;
		}
		next[i] = k;
	}
	return next;
}

// 匹配DNA和酶
// a为DNA串,b为酶串(去掉"^"),cutIndex为酶切位置,next为酶对应的next表 
void KMP(string a, string b, int cutIndex, vector<int> next)
{
	if (find(ans.begin(), ans.end(), a) == ans.end()) // 确保只记录一次 
	{
		ans.push_back(a); // 先将自身记录在酶切结果中 
	}
	else
	{
		return; // 之前已经有过这个DNA片段的继续酶切结果 
	}
	
	int bLength = b.size();
	int k = 0;
	for (int i = 0; i < a.size(); i++)
	{
		while(k > 0 && a[i] != b[k])
		{
			k = next[k - 1];
		}
		
		if (a[i] == b[k])
		{
			k++;
		}
		
		if (k == bLength) // 匹配成功 
		{
			// 获取酶切后的左右两串DNA 
			string a1 = a.substr(0, i - (bLength - cutIndex)),
			a2 = a.substr(i - (bLength - cutIndex), a.size() - 1);
			
			// *关键步骤 
			// 对两段酶分别再次使用所有酶酶切，来获取所有可能 
			for (int j = 0; j < meis.size(); j++)
			{
				KMP(a1, meis[j], cutIndexs[j], nexts[j]);
				KMP(a2, meis[j], cutIndexs[j], nexts[j]);
			}
			
			break; // 每次KMP匹配只酶切一次 
		}
	}
}

int main()
{
	int n;
	cin >> n; // 酶的数量 
	for (int i = 0; i < n; i++)
	{
		string str, mei = "";
		cin >> str;
		for (int j = 0; j < str.size(); j++)
		{
			if (str[j] == '^')
			{
				cutIndexs.push_back(j + 1); // 记录酶切位置 
			}
			else
			{
				mei.push_back(str[j]); // 构建去"^"酶 
			}
		}
		
		meis.push_back(mei); // 记录酶的串 
		nexts.push_back(build_next(mei)); // 记录酶对应的next表 
	}
	
	string DNA;
	cin >> DNA; // 输入DNA串 
	
	// 对整条DNA使用每种酶进行酶切 
	for (int i = 0; i < meis.size(); i++)
	{
		KMP(DNA, meis[i], cutIndexs[i], nexts[i]);
	}
	
	
	sort(ans.begin(), ans.end()); // 字典升序排列 
	for (int i = 0; i < ans.size(); i++)
	{
		cout << ans[i] << endl; // 输出酶切结果 
	}
	return 0;
}