题目地址:https://nanti.jisuanke.com/t/41395

题目:


给出长度为n的字符串s,长度为m的字符串t,在s中找出最长的子序列q,使得q的字典序比t大,如果不存在这样一个子序列q,输出-1,否则输出q的长度

 

解题思路:


对于t串中的t[i]:

(1)若在s串中能够找到一个大于t[i]的字符s[j],那么s串中s[j]之后(包括s[j])的字符都可取,且j一定是在 s中和t[i-1]相同的字符 的后面,计算出这个子序列对应的长度,更新答案;

(2)若能在s串中找到一个和t[i]相等的s[j], 那么标记这个s[j]的位置为last,继续向下查询。

(3)如果s串中没有和t[i]相等的,那么s串中的子序列对应位置上只能选一个比t[i]大的,不再向下处理。

如果能在s串中找到一个和t完全相同的子序列且s串中末尾还有剩余的字符,说明还存在一个满足条件的子序列,更新答案。

每次都应先考虑能否在s串中找到一个大于t[i]的,因为若s串中不存在和t[i]相等的字符时就结束处理了,但是此时s中可能还存在大于t[i]的字符,对应的子序列长度是要参与答案统计的。

两组特殊的测试样例:

(1)cba cba

(2)cbaa cba

 

ac代码:


#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n,m;
char s[maxn],t[maxn];
vector<int> pos[30];
int main()
{
    scanf("%d %d", &n, &m);
    scanf("%s", s);
    scanf("%s", t);
    for(int i = 0; i < n; i++)
        pos[s[i]-'a'].push_back(i);
    int last = -1, ans = -1;
    bool all = true;//在s串中存在一个子序列和t串相同
    for(int i = 0; i < m; i++)
    {
        int p = t[i]-'a';
        for(int k = p+1; k < 26; k++)//比t[i]大的
        {
            auto it = upper_bound(pos[k].begin(), pos[k].end(), last);//在last之后第一个k+'a'的下标
            if(it != pos[k].end())ans = max(ans, n - *it + i);//能找到,it后面的字符全取
        }
        auto it = upper_bound(pos[p].begin(), pos[p].end(), last);
        if(it == pos[p].end())//没有找到=t[i]的,只能取大于t[i]的,后续不用处理了
        {
            all = false;
            break;
        }
        last = *it;
    }
    if(all && last != n-1)//s串中存在和t串相同的子序列,且s中还有剩余的字母
        ans = max(ans, m + n - last - 1);
    printf("%d\n", ans);
    return 0;
}