MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 10340 - All in All
AOAPC II

UVaOJ 10340 - All in All

Chai
2021-11-24 0:00:00在线评测阅读 269

问题描述

p10340

原题链接:UVaOJ 10340 - All in Alls

相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-9

解法一:双指针

只要 s 是 t 的题目描述的子串,那么对任意的 $s_{i}$ 和 $s_{j}$, 其中 $i <j$; 一定存在 $p < q$, 满足 $t_{p} < t{q}$. 根据顺序特性,使用两个指针对字符串进行扫描,看最终 s 中的所有字符能否在 t 中顺序出现。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  string s, t;
  while (cin >> s >> t) {
    int p1 = 0, p2 = 0;
    while (p1 < s.length() && p2 < t.length())
      s[p1] == t[p2] ? p1++, p2++ : p2++;
    cout << (p1 == s.length() ? "Yes" : "No") << endl;
  }
  return 0;
}
Python
1
2
3
4
5
6
7
8
9
10
11
while True:
    try:
        s, t = input().split()
        p1 = p2 = 0
        while (p1 < len(s) and p2 < len(t)):
            if s[p1] == t[p2]:
                p1 += 1
            p2 += 1
        print("Yes" if p1 == len(s) else "No")
    except EOFError:
        break
AOAPC II UVaOJ 双指针 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz