题解 | #最长公共子序列(二)#

static const auto io_sync_off = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    
    string LCS(string s1, string s2) {
        if(s1.empty()||s2.empty()) return "-1";
        vector<vector<int> > hashTable(128,vector<int>());
        vector<int> A;
        for(int i=0;i<s1.size();++i){
            //char作下标，转化为ASCII码
            hashTable[s1[i]].push_back(i);
        }
        for(int i=0;i<s2.size();++i){
            int n=hashTable[s2[i]].size()-1;
            for(int j=0;j<=n;++j){
                A.push_back(hashTable[s2[i]][n-j]);
            }
        }
        
        int N=A.size();
        if(!N) return "-1"; 
        //top:最长上升子序列记录数组
        //topIndexs:以i结尾的子序列最大长度
        //pre:从后往前顺序指向前一个上升节点
        vector<int> top(N,0),topIndexs(N,0);
        top[0]=A[0];
        int ans=0;
        for(int i=0;i<N;++i)
        {
            //在顺序数组找到大于A[i]的第一个数(二分查找)
            int pos=lower_bound(top.begin(),top.begin()+ans,A[i])-top.begin();
            top[pos]=A[i];
            topIndexs[i]=pos+1;
            if(pos==ans)
                ++ans;
        }
        vector<int> pre(ans);
        for(int i=A.size()-1,j=ans;i>=0;--i){
            if(topIndexs[i]==j)
                pre[--j]=A[i];
        }
        string seq(ans,0);
        for(int i=0;i<ans;++i){
            seq[i]=s1[pre[i]];
        }
        return seq;
    }
    
};