求最长公共子序列

亦凉 2022-08-04 04:26 186阅读 0赞

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。

#include "stdafx.h"
    #include<deque>
    #include<iostream>
    
    using namespace std;
    
    deque<pair<char, int>>common;
    deque<pair<char, int>>max;
    deque<deque<pair<char, int>>>aa;
    int k = 0;//在str2中找到obj的位置
    int kk;
    
    
    
    deque<pair<char, int>>char2vec(char*str, int offset)
    {
    	deque<pair<char, int>>aa;
    	while (*str != '\0')
    	{
    		aa.push_back(pair<char, int>(*str, offset));
    		str++;
    		offset++;
    	}
    	return aa;
    }
    
    int find_char(char obj, char*str, int startpos)
    {
    	int len = strlen(str);
    	while (startpos < len)
    	{
    		if (str[startpos] == obj)
    			return startpos;
    		startpos++;
    	}
    	return -1;
    }
    
    
    void forward(char*str1, char*str2, int n)
    {
    	int len1 = strlen(str1);
    	int len2 = strlen(str2);
    	while (n < len1&&k < len2 - 1)
    	{
    		kk = find_char(str1[n], str2, k);
    		if (kk >= 0)
    		{
    			common.push_back(pair<char, int>(str1[n], kk));
    			k = kk;
    			//if (n<len1 - 1)
    			aa.push_back(char2vec(str1 + n + 1, n + 1));
    		}
    		n++;
    	}
    }
    
    
    void LMS(char*str1, char*str2)
    {
    	int len1 = strlen(str1);
    	int len2 = strlen(str2);
    	if (len1 > len2)
    	{
    		char*temp = str1;
    		str1 = str2;
    		str2 = temp;
    		int tt = len1;
    		len1 = len2;
    		len2 = tt;
    	}
    	int maxlen = 0;
    	int n = 0;//str1的索引
    
    	forward(str1, str2, n);
    	if (common.size() > maxlen)
    	{
    		maxlen = common.size();
    		max = common;
    	}
    	while (!aa.empty())
    	{
    		if (aa.back().empty())
    		{
    			aa.pop_back();
    			common.pop_back();
    			if (aa.empty())
    				return;
    		}
    		if (common.size() > 1)
    		{
    			k = common[common.size() - 2].second + 1;
    		}
    		else
    		{
    			k = 0;
    		}
    		kk = find_char(aa.back().front().first, str2, k);
    		if (kk >= 0)
    		{
    			common.pop_back();
    			common.push_back(aa.back().front());
    			common.back().second = kk;//find_char(common.back().first, str2, common[common.size() - 2].second + 1);
    			k = kk;
    			n = aa.back().front().second;
    			aa.back().pop_front();
    			forward(str1, str2, n + 1);
    			if (common.size() > maxlen)
    			{
    				maxlen = common.size();
    				max = common;
    			}
    		}
    		else
    		{
    			aa.back().pop_front();
    			if (aa.back().empty())
    			{
    				aa.pop_back();
    				common.pop_back();
    			}
    
    		}
    	}
    
    }
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	char*str1 = "adecfbaf";
    	char*str2 = "deabcabaf";
    
    	LMS(str1, str2);
    	for (int i = 0; i < max.size(); i++)
    		cout << max[i].first << endl;
    	system("pause");
    	return 0;
    }

上述算法中common中存放当前找到的子序列，common里的pair<char,int>里的int代表这个字符在str2中的位置，

aa中存放的是未被遍历过的字符，aa里的pair<char,int>里的int代表这个字符在str1中的位置。

整个搜索过程是波浪式前进，common找到一个起点，走到结尾，然后替换common的结尾，再往前走，走到结尾再替换

反复执行，过程中记录common的最大长度即可