【PAT甲级】1177 Subsequence in Substring(25分)[判断子序列,暴力,双指针]

news/2024/6/17 4:07:23 标签: 算法, c++, 开发语言

问题思考:

  • 用字符串暴力匹配的思路,能过。
  • 用模式串匹配母串,扫描一遍母串,只要模式串第一位匹配上,就往后判断保住子序列所需子串的长度(判断子序列可以用双指针法)。
  • 过程中间记录最短的符合要求的子串。比较更新,最后输出结果即可。

代码实现:

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

int main() {
    string s, p;
    cin >> s >> p;
    int n = s.length(), m = p.length();
    string ans = s;    // 存储子串
    int l = n;    // 记录子串的长度
    for (int i = 0; i <= n - m; i++) {
        // 每次遇到子序列的起点,就往后判断子串所需长度
        if (s[i] == p[0]) {
            string sub = "";
            int j = i, k = 0; // 双指针法判断子序列
            while (k < m) {
                if (s[j] == p[k]) k++;
                sub += s[j];
                j++;
            }
            if (l > sub.size()) {    // 记录长度最小的子串
                ans = sub;
                l = ans.size();
            }
        }
    }
    cout << ans;
    return 0;
}


http://www.niftyadmin.cn/n/5333044.html

相关文章

达梦数据库 忘记 SYSDBA 密码 处理方法

DM 提供数据库身份验证模式、基于操作系统的身份验证模式、外部身份验证模式和 UKEY 身份验证模式来保护对数据库访问的安全。数据库身份验证模式需要利用数据库口令&#xff0c; 即在创建或修改用户时指定用户口令&#xff0c;用户在登录时输入对应口令进行身份验证;基于操作 …

VR远程的实现

VR远程是一种使用虚拟现实&#xff08;VR&#xff09;技术进行远程操作的方法。通过VR设备&#xff0c;用户可以在虚拟环境中进行操作&#xff0c;并远程控制物理设备或机器人。 VR远程的实现通常需要以下几个步骤&#xff1a; 建立虚拟环境&#xff1a;使用VR技术创建一个与…

基于若依的ruoyi-nbcio流程管理系统修复自定义业务表单的收回功能

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a; https://gitee.com/nbacheng/n…

Spring06

一、SpirngMvc的基本概念 Spring MVC 是 Spring 提供的一个基于 MVC 设计模式的轻量级 Web 开发框架&#xff0c;本质上相当于 Servlet。 MVC&#xff08;Model View Controller&#xff09;&#xff0c;一种用于设计创建Web应用程序的开发模式 Model&#xff08;模型&#xff…

238.【2023年华为OD机试真题(C卷)】火星文计算(模拟-JavaPythonC++JS实现)

🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(Java&Python&C++&JS分别实现),详细代码讲解,助你深入学习,深度掌握! 文章目录 一. 题目-火星文计算二.解题思路三.题解代码Python题解代…

修改iview的表格table展开的默认icon和样式

修改前 修改后 修改内容 .title_label_list .ivu-icon-ios-add{font-size: 26px;color: #888888; } .title_label_list .ivu-icon-ios-add:hover{color: #11AAAA; } .title_label_list .ivu-icon-ios-add:before {content: "\F341"; } .title_label_list .ivu-icon-…

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK使用相机日志跟踪功能(C++)

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK使用相机日志跟踪功能&#xff08;C&#xff09; Baumer工业相机Baumer工业相机NEOAPI SDK和短曝光功能的技术背景Baumer工业相机通过NEOAPI SDK使用相机日志跟踪功能1.引用合适的类文件2.通过NEOAPI SDK使用相机日志跟踪功能3.通…

Golang leetcode151 翻转字符串中的单词 双指针 常规+进阶

翻转字符串中的单词 leetcode151 常规做法 双指针 func reverseWords(s string) string { WordList : []string{} left : 0 L : len(s) //fmt.Println(L)for i, i2 : range s {//去除重复的空格if i > 0 && s[i-1] && i2 {leftcontinue}//不为空格时…