华为OD机试真题-字符串序列判定-2024年OD统一考试（C卷D卷）

忘是亡心i 2024-04-27 15:36 7阅读 0赞

> **题目描述：**
> 
> 输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。判定S是否是L的有效字串。
> 
> 判定规则：S中的每个字符在L中都能找到（可以不连续），且S在Ｌ中字符的前后顺序与S中顺序要保持一致。（例如，S="ace"是L="abcde"的一个子序列且有效字符是a、c、e，而"aec"不是有效子序列，且有效字符只有a、e）
> 
> **输入描述：**
> 
> 输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。先输入S，再输入L，每个字符串占一行。
> 
> **输出描述：**
> 
> S串最后一个有效字符在L中的位置。（首位从0开始计算，无有效字符返回-1）
> 
> 补充说明：
> 
> **示例1**
> 
> 输入：ace
> 
> abcde
> 
> 输出：4
> 
> 说明：
> 
> **示例2**
> 
> 输入：fgh
> 
> abcde
> 
> 输出：-1
> 
> 说明：

**题目解析**：这是一道字符串子序列匹配问题，查询某一字符串是否在另一字符串的子序列中，输出最后一个匹配的字符的位置，我们只需要顺序遍历s和l，模拟字符串的匹配，逐字符检查 s 是否作为 l 的子序列出现，并在找到匹配时更新索引位置。这种解法是线性的，因为它只需遍历一次字符串 l，使得时间复杂度为 O(n)，其中 n 是字符串 l 的长度。

C++解法：

#include <iostream> 
    #include <string>   
    using namespace std; 
    
    int main(){
        string s, l;       // 声明两个字符串s和l
        cin >> s >> l;     // 从标准输入读取两个字符串到s和l
        int last_idx = -1; // 初始化last_idx为-1，表示找不到时的返回值
        int m = s.length(); // 计算字符串s的长度
        int n = l.length(); // 计算字符串l的长度
        int to_match = 0;   // 初始化匹配的位置为0
    
        // 遍历字符串l
        for (int i = 0; i < n; i++) {
            if (s[to_match] == l[i]) // 如果当前字符匹配
                to_match++, last_idx = i; // 增加匹配位置，更新最后匹配的索引
            if (to_match >= m) break; // 如果全部字符都已匹配，则退出循环
        }
    
        cout << last_idx; // 输出最后匹配的索引位置
        return 0; // 程序结束
    }

Java解法：

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String s = scanner.next(); // 读取第一个字符串到s
            String l = scanner.next(); // 读取第二个字符串到l
            scanner.close();
    
            int lastIdx = -1; // 初始化lastIdx为-1，表示找不到时的返回值
            int m = s.length(); // 获取字符串s的长度
            int n = l.length(); // 获取字符串l的长度
            int toMatch = 0;   // 初始化要匹配的位置为0
    
            // 遍历字符串l
            for (int i = 0; i < n; i++) {
                if (toMatch < m && s.charAt(toMatch) == l.charAt(i)) { // 如果当前字符匹配
                    toMatch++; // 增加匹配的位置
                    lastIdx = i; // 更新最后匹配的索引
                }
                if (toMatch >= m) break; // 如果全部字符都已匹配，则退出循环
            }
    
            System.out.println(lastIdx);
        }
    }

python解法：

def main():
        s = input()
        l = input()
        last_idx = -1  # 初始化last_idx为-1，表示找不到时的返回值
        to_match = 0  # 初始化要匹配的位置为0
        m = len(s)  # 获取字符串s的长度
        n = len(l)  # 获取字符串l的长度
    
        # 遍历字符串l
        for i in range(n):
            if to_match < m and s[to_match] == l[i]:  # 如果当前字符匹配
                to_match += 1  # 增加匹配的位置
                last_idx = i  # 更新最后匹配的索引
            if to_match >= m:  # 如果全部字符都已匹配，则退出循环
                break
    
        print(last_idx)  # 输出最后匹配的索引位置
    
    if __name__ == "__main__":
        main()