E. Expenditure Reduction（思维+预处理+蛮力）

题面如下：

题意简说：

给你两个字符串：$sandt$
$t是s的子序列$
找 最小长度字符串 $str$
使 $str$ 满足 是 $s$的子串 && 使 $t$ 是 $str$ 的子序列

思路 or 题解

因为 $t$串长度最多100， 所以我们可以通过$t$串的位置进行求解
我们可以预处理$s$串， 在 $i$ 位置向右最近的 字符 $ch$ 的位置
约定：$s$串长度为$n$， $t$串长度为$m$
预处理的时间复杂度为 $O(n\ast 36)$

这样我们就可以在 $O(n\ast m)$的时间复杂度 去计算出每一个合法区间的长度
合法区域长度最小的区间就是我们求的最优解！

AC代码如下：

const int N = 100009;
string a, b;
int lena, lenb;
int ne[N][45];
int cal(char ch)
{
    if (ch >= '0' && ch <= '9')
        return ch - '0' + 1;
    else
        return ch - 'a' + 11;
}
void init()
{
    for (int i = 0; i <= lena; i++)
        for (int j = 1; j < 40; j++)
            ne[i][j] = 0;
}
void solve()
{
    cin >> a >> b;
    lena = a.size(), lenb = b.size();
    init();
    a = '#' + a;
    b = '#' + b;
    for (int i = lena - 1; i >= 1; i--)
    {
        for (int j = 1; j < 40; j++)
            ne[i][j] = ne[i + 1][j];
        ne[i][cal(a[i + 1])] = i + 1;
    }

    int mn = INT_MAX, idx;
    for (int i = 1; i <= lena; i++)
    {
        if (a[i] != b[1])
            continue;
        int now = i;
        bool f = 1;
        for (int j = 2; j <= lenb; j++)
        {
            if (ne[now][cal(b[j])])
                now = ne[now][cal(b[j])];
            else
            {
                f = 0;
                break;
            }
        }
        if (f)
        {
            if (now - i + 1 < mn)
            {
                mn = now - i + 1;
                idx = i;
            }
        }
    }
    for (int i = idx; i <= idx + mn - 1; i++)
        cout << a[i];
    cout << '\n';
}
int main()
{
    buff;
    int _;
    cin >> _;
    while (_--)
        solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69