跳到主要内容

删除字符串

题目描述​

公司里有两个字符串，分别是 s和 t。由于数据安全的原因，字符串 t不允许作为 s的子串存在。

为了满足数据规范，米小游需要按照一定的顺序删除字符串 s中的一些字符，确保s中不再包含t。

注意删除字符 si后，不会自动将前后字符串合并，你可以认为使用一个 空白字符代替 si。

米小游想知道，在保证 s不包含 t的前提下，她最少需要删除多少个字符？

删除顺序可以描述为一个排列，ai表示删除 s[ai]字符。

输入描述​

第一行输入两个整数 n和 m，表示字符串 s和 t的长度。

第二行输入一个长度为 n的字符串，仅包含小写字母。

第三行输入一个长度为 m的字符串，仅包含小写字母。

第四行输入一个长度为 n的排列，表示第 i次删除 s[ai]字符。

1≤n≤10^5 1≤m≤50 1≤ai≤n

输出描述​

输出一个整数，表示最少需要删除的字符个数。

示例​

输入：
5 2
ababa
ab
3 2 5 4 1

输出：
2

解释：
第一次删除`S3`，`s`变为`ab(a)ba`。
第二次删除`S2`，`s`变为`a(ba)ba`。
此时`s`不包含`t`，最少需要删除2个字符。

解题思路​

贪心算法

  1. 遍历字符串 s，判断 s是否包含 t
  2. 如果包含，则删除s中包含t的第一个字符，并继续判断 s是否包含 t
  3. 如果不包含，则返回 s的长度

时间复杂度：O(n²) 空间复杂度：O(n)

C++ 解法​

#include <iostream>
#include <string>
#include <vector>

bool containSubString(const std::string &s, const std::string &t)
{

    int n = s.length();
    int m = t.length();

    for (int i = 0; i <= n - m; ++i)
    {
        bool found = true;
        for (int j = 0; j < m; ++j)
        {
            // 如果当前位置是空格或字符不匹配，则不是有效的子串
            if (s[i + j] == ' ' || s[i + j] != t[j])
            {
                found = false;
                break;
            }
        }
        if (found)
            return true;
    }
    return false;
}

int main()
{
    int n, m;
    std::cin >> n >> m;

    std::string s, t;
    std::cin >> s >> t;

    std::vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

    std::string current = s;
    int deletCount = 0;

    for (int i = 0; i < n; i++)
    {
        // 删除字符(用空格代替)
        current[nums[i] - 1] = ' ';
        deletCount++;

        if (!containSubString(current, t))
        {
            break;
        }
    }

    std::cout << deletCount << endl;
    return 0;
}