字符串

方案1: 暴力求解

记得之前有类似的题目,可以用dp

满分代码

/**
题意: 字符串中,找子字符串,子字符串中包含子序列

方案1: 暴力求解
*/
#include <cstring>
#include <iostream>

using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
    string str, seq, res;
    cin >> str >> seq;
    int len = INF;
    for(int i = 0; i < str.length(); i++)
    {
        int j = i, k = 0;
        while (j < str.length() && str[j] != seq[k]) j++;
        int l = j;
        for(;k < seq.length() && j < str.length(); j++)
        {
            if (str[j] == seq[k]) k++;
        }
        if (k == seq.length())
        {
            if (j - l < len) len = j - l, res = str.substr(l, j - l);
        }
    }
    cout << res;
}