E - 目标字符串fefwefevw

Question

E - 目标字符串
时间限制：1 s内存限制：256 MB
有一个长度为
n 的字符串
s，下标从

1 开始，现在
ℎ
chuck 需要利用这个字符串
s 去收集字符，具体的，从下标

[1,n] 中选择一个位置

start 作为起点，从当前位置先往后面走

x(0≤x) 步（不能走出边界，即不能大于
n），之后在往前面走

y(0≤y) 步（不能走出边界，即不能小于
1 ）。对于每个经过的位置，我们都会收集该位置对应的字母（假设每个位置字母是无限的），并按收集顺序得到字符串
B。

比如长度为
4
4 的字符串为
abcd，选定第二个位置作为起始位置，往后走
2
2 步，之后往前走
1
1 步，依次走过的位置为 2->3->4->3 。然后收集到的字符依次为 “bcdc”，即
=
B=bcdc。

现在给定一个字符串
A 和
C，
ℎ

chuck 想知道能不能通过上述的方式，最终得到的字符串
B 等于
C。
c++

Answer 1

EternalLBZ 晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

问题的解决思路如下：

1. 遍历字符串A，找到与字符串C的第一个字符相等的位置start。
2. 计算从start开始向后走的步数x和向前走的步数y。
3. 根据x和y的值，判断是否可以得到字符串C。具体方法是：
   • 如果x小于等于y，那么需要满足条件x <= n - start和y <= start - 1，即向后移动的步数不能超过剩余字符的个数，向前移动的步数不能超过已经经过的字符的个数。
   • 如果x大于y，那么需要满足条件x <= n - start + y和y <= start - 1，即向后移动的步数不能超过剩余字符的个数和已经经过的字符的个数的和。

根据以上思路，可以通过以下方式来解决问题：

#include <iostream>
#include <string>
using namespace std;

bool canObtain(string A, string C) {
    int n = A.length();
    int m = C.length();
    if (n < m) {
        return false;
    }

    for (int start = 0; start < n; start++) {
        int x = 0;
        int y = 0;
        for (int i = start; i < n; i++) {
            if (A[i] == C[x]) {
                x++;
            }
            if (x == m) {
                return true;
            }
        }
        for (int i = start - 1; i >= 0; i--) {
            if (A[i] == C[m - 1 - y]) {
                y++;
            }
            if (x + y == m) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    string A, C;
    cin >> A >> C;
    if (canObtain(A, C)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

以上代码通过遍历字符串A的所有可能的起始位置start，并同时记录向后移动的步数x和向前移动的步数y，然后判断x和y是否满足条件。如果存在一个起始位置start满足条件，说明可以通过指定的移动方式得到字符串C，返回true；否则返回false。