P8697 [蓝桥杯 2019 国 C] 最长子序列 题解

Lovely_Chtholly · 2023-03-31 13:19:43 · 题解

【分析】

题意题面已经写得很清楚了，我们只需要思考如何求解即可。

容易想到，本题可以直接从两字符串头开始遍历，逐个寻找相同的字符即可，具体实现方法如下：

1. 设置两个循环变量 i 和 j，分别代表 S 和 T 的下标。

2. 如果 S_i=T_j，则可继续遍历两字符串，并将答案 +1。

3. 否则，只需要继续遍历 S 字符串即可。

【AC 代码】

#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
int ans;
string s,t;
signed main()
{
    cin>>s>>t;
    for(int i=0,j=0;i<s.size()and j<t.size();i++)
        if(s[i]==t[j])j++,ans++;
    printf("%d",ans);
    return 0;
}