南宁网站seo优化公司/深圳seo优化seo优化
题目：
题目链接 ：登录—专业IT笔试面试备考平台_牛客网
题目所求为s中能删除t的最大次数
其实是贪心的思想
思路1：对于s字符串中取最大的t字符串
我们可以用一个数组记录下t字符串中
每个字符出现的顺序
再遍历s数组
对于s数组中每个在t中有的字符
出现的次数进行统计
但是要注意设计限制条件
当遍历s时每次s的字符
统计出现的次数时要小于它在
t中的位置的前一个字符的数量
这样就可以达到对所有满足条件的结果进行统计
（原因：相当于按照t字符串的顺序进行统计）
思路2：假设我们在s字符串中最大能删除n次字符串
那么我们要怎么删才能达到删除n次字符串勒
答案是从第n次字符串开始删除
并且第n次字符后面所有的字符都可以删除(对次数无影响)
然后删除n-1次的字符串
然后依次往前删除
这样就可以保证能删除完n次所有的字符串
（原因：每次从后往前的删除就保证了
对前面满足条件的字符串不造成影响
依次的删除就能保证达到最大删除次数）
思路1代码详解：
#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long ll;
#include<string.h>
using namespace std;
int n, m;
int pos[30], ans[30];
string s, t;
int main()
{int ts;cin >> ts;while (ts--){scanf("%d%d", &n, &m);memset(pos, -1, sizeof(pos));memset(ans, 0, sizeof(ans));//每次样例都需初始化数组cin >> s >> t;for (int i = 0; i < m; i++) pos[t[i] - 'a'] = i;//记录下t数组里面每个字符出现的顺序for (int i = 0; i < n; i++){if (s[i] == t[0]) ans[0]++;//对于t的第一个字符出现的数量进行统计else{int step = pos[s[i] - 'a'];if (step!= -1 && ans[step] < ans[step - 1])ans[step]++;//代码关键！如果s中的该字符存在于t中，并且出现的次数小于该字符在t中的前一个字符。那么该次数可以加1}}printf("%d\n", ans[m - 1]);//输出最后满足t顺序条件的字符串数量}return 0;
}思路2代码（官方代码）：
#include <bits/stdc++.h> typedef unsigned long long ull; typedef long long ll; #define inf 0x3f3f3f3f #define rep(i, l, r) for (int i = l; i <= r; i++) #define nep(i, r, l) for (int i = r; i >= l; i--) void sc(int &x) { scanf("%d", &x); } void sc(int &x, int &y) { scanf("%d%d", &x, &y); } void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); } void sc(ll &x) { scanf("%lld", &x); } void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); } void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); } void sc(char *x) { scanf("%s", x); } void sc(char *x, char *y) { scanf("%s%s", x, y); } void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); } void out(int x) { printf("%d\n", x); } void out(ll x) { printf("%lld\n", x); } void out(int x, int y) { printf("%d %d\n", x, y); } void out(ll x, ll y) { printf("%lld %lld\n", x, y); } void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); } void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); } void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);} using namespace std; const int N=1e6+5,mod=998244353; int n,m; char s[N],t[N]; int main() {// freopen("1.in", "r",stdin);// freopen("1.out", "w", stdout);int ts;sc(ts);ast(ts,1,10000);int sum=0;while(ts--){scanf("%d%d",&n,&m);sc(s+1);sc(t+1);ast(n,1,1000000);ast(m,1,min(n,26));sum+=n;ast(sum,1,1000000);assert(strlen(s+1)==n);assert(strlen(t+1)==m);rep(i,1,n) ast(s[i],'a','z');rep(i,1,m) ast(t[i],'a','z');for(int i=1;i<=m;i++)for(int j=i+1;j<=m;j++) assert(t[i]!=t[j]);vector<int>vc[26];rep(i,1,n)vc[s[i]-'a'].emplace_back(i);int ans=0;while(true){bool flag=true;int las=n+1;for(int i=m;i>=1;i--){while(vc[t[i]-'a'].size()&&vc[t[i]-'a'].back()>=las) vc[t[i]-'a'].pop_back();if(vc[t[i]-'a'].empty()){flag=false;break;}las=vc[t[i]-'a'].back();vc[t[i]-'a'].pop_back();}if(!flag) break;ans++;}out(ans);} }
PS:苟利国家生死以，岂因祸福避趋之！____林则徐《赴戍登程口占示家人·其二》