本文主要是介绍最长公共子序列补充题型：判断是否是子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
🧊🧊🧊新题型
最长公共子序列是基于动态规划思想，判断子序列长度的，这种方法的弊端就是dp需要很大，如果字符串长度很长就会超出内存限制。这里我们补充一种字符串很长的题型：给出字符串s和字符串t，问s通过删除一些字符能否变成t。简言之，就是t是否是s的非连续子字符串。
这种题目的思想其实很简单，只需要遍历两个字符串然后判断即可，具体我们来看下边这一道题目：
这道题目就是这样的题目，我们来看解决代码：
#include<bits/stdc++.h>
using namespace std;
char s[100005],t[100005];
int head=1,len;
int main( )
{scanf("%s%s",s+1,t+1);len=strlen(s+1);for(int i=1;i<=len;i++){if(s[i]==t[head]) head++;}if(head>strlen(t+1)) cout<<"Lucky!";else cout<<"QAQ Unlucky!";return 0;
}如果有相等的字符，就后移，最后判断有多少相等的字符。
🧊🧊🧊补充：最长公共子序列模板
#include <bits/stdc++.h>
using namespace std;
int dp[101][101];
int main() {string a, b;memset(dp, 0, sizeof(dp));cin >> a >> b;int lena = a.size();int lenb = b.size();for(int i = 1; i <= lena; ++i) {for (int j = 1; j <= lenb; ++j) {if(a[i - 1] == b[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}cout << dp[lena][lenb] << endl;return 0;
}
好了，今天就补充到这啦，加油加油！( •̀ ω •́ )✧
这篇关于最长公共子序列补充题型：判断是否是子字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
