题解 | 最强大脑

解题思路

这是一个字符串匹配的问题。需要判断小B看到的两段颜色序列是否能在完整的车站颜色序列中按顺序找到，并且判断可能的行进方向。

关键点：

需要考虑正向和反向两种情况
两段观察序列必须按顺序出现且不能重叠
需要处理多组测试数据
同一个字符可能出现多次

算法步骤：

读取完整的车站颜色序列
读取两次观察到的颜色序列
分别判断正向和反向是否可能
根据判断结果输出对应方向

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string solve(string& stations, string& first, string& second) {
        string reversed = stations;
        reverse(reversed.begin(), reversed.end());
        
        bool forward = check(stations, first, second);
        bool backward = check(reversed, first, second);
        
        if (forward && backward) return "both";
        if (forward) return "forward";
        if (backward) return "backward";
        return "invalid";
    }
    
private:
    bool check(string& s, string& first, string& second) {
        int n = s.length();
        // 尝试所有可能的第一段序列位置
        for (int i = 0; i < n; i++) {
            int pos1 = i;
            int j = 0;
            // 匹配第一段序列
            while (j < first.length() && pos1 < n) {
                if (s[pos1] == first[j]) {
                    j++;
                }
                pos1++;
            }
            if (j == first.length()) {  // 第一段匹配成功
                // 从第一段结束位置开始匹配第二段
                int pos2 = pos1;
                j = 0;
                while (j < second.length() && pos2 < n) {
                    if (s[pos2] == second[j]) {
                        j++;
                    }
                    pos2++;
                }
                if (j == second.length()) {  // 第二段也匹配成功
                    return true;
                }
            }
        }
        return false;
    }
};

int main() {
    string stations, first, second;
    Solution solution;
    while (cin >> stations >> first >> second) {
        cout << solution.solve(stations, first, second) << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private boolean check(String s, String first, String second) {
            int n = s.length();
            // 尝试所有可能的第一段序列位置
            for (int i = 0; i < n; i++) {
                int pos1 = i;
                int j = 0;
                // 匹配第一段序列
                while (j < first.length() && pos1 < n) {
                    if (s.charAt(pos1) == first.charAt(j)) {
                        j++;
                    }
                    pos1++;
                }
                if (j == first.length()) {  // 第一段匹配成功
                    // 从第一段结束位置开始匹配第二段
                    int pos2 = pos1;
                    j = 0;
                    while (j < second.length() && pos2 < n) {
                        if (s.charAt(pos2) == second.charAt(j)) {
                            j++;
                        }
                        pos2++;
                    }
                    if (j == second.length()) {  // 第二段也匹配成功
                        return true;
                    }
                }
            }
            return false;
        }
        
        public String solve(String stations, String first, String second) {
            StringBuilder sb = new StringBuilder(stations);
            String reversed = sb.reverse().toString();
            
            boolean forward = check(stations, first, second);
            boolean backward = check(reversed, first, second);
            
            if (forward && backward) return "both";
            if (forward) return "forward";
            if (backward) return "backward";
            return "invalid";
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Solution solution = new Solution();
        
        while (sc.hasNext()) {
            String stations = sc.next();
            String first = sc.next();
            String second = sc.next();
            System.out.println(solution.solve(stations, first, second));
        }
        
        sc.close();
    }
}

class Solution:
    def check(self, s: str, first: str, second: str) -> bool:
        n = len(s)
        # 尝试所有可能的第一段序列位置
        for i in range(n):
            pos1 = i
            j = 0
            # 匹配第一段序列
            while j < len(first) and pos1 < n:
                if s[pos1] == first[j]:
                    j += 1
                pos1 += 1
            if j == len(first):  # 第一段匹配成功
                # 从第一段结束位置开始匹配第二段
                pos2 = pos1
                j = 0
                while j < len(second) and pos2 < n:
                    if s[pos2] == second[j]:
                        j += 1
                    pos2 += 1
                if j == len(second):  # 第二段也匹配成功
                    return True
        return False

    def solve(self, stations: str, first: str, second: str) -> str:
        reversed_stations = stations[::-1]
        
        forward = self.check(stations, first, second)
        backward = self.check(reversed_stations, first, second)
        
        if forward and backward:
            return "both"
        if forward:
            return "forward"
        if backward:
            return "backward"
        return "invalid"

# 读取输入
while True:
    try:
        stations = input()
        first = input()
        second = input()
        solution = Solution()
        print(solution.solve(stations, first, second))
    except EOFError:
        break

算法及复杂度

算法：字符串匹配
时间复杂度： $\mathcal{O(N^2)}$ ，其中 $N$ 为车站序列长度
空间复杂度： $\mathcal{O(N)}$ ，用于存储反向序列