4382. 快速打字-Toy模板网

这篇具有很好参考价值的文章主要介绍了4382. 快速打字。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Link

4382. 快速打字

题意

芭芭拉是一个速度打字员。
为了检查她的打字速度，她进行了一个速度测试。
测试内容是给定她一个字符串 I，她需要将字符串正确打出。
但是，芭芭拉作为一个速度打字员，在追求速度的同时，难免会发生一些错误，按错一些按键。
最终，芭芭拉打出的字符串为 P
现在，芭芭拉想知道，能否仅通过删除一些额外字母的方式，将字符串 P变为字符串 I
如果可以，则输出需要删除的字母数量，如果不行，则输出 IMPOSSIBLE。
思路

双指针，锁定I字符串的某一字符，遍历P的字符，遇到相同的再继续一起往下遍历，否则走到底，走出去了就是不可能文章来源地址https://www.toymoban.com/news/detail-536253.html

代码

'''
Author: NEFU AB-IN
Date: 2023-07-08 21:41:05
FilePath: \Acwing\4382\4382.py
LastEditTime: 2023-07-09 00:24:30
'''
# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor


class sa:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __lt__(self, a):
        return self.x < a.x


# Final
N = int(1e5 + 10)
M = 20
INF = int(2e9)

# Define
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
AR = lambda x=0: [x] * N

# —————————————————————Division line ——————————————————————

t, = read()

for _ in range(t):
    I = input()
    p = input()

    j, cnt, flag = 0, 0, 0
    for i in range(len(I)):
        while j < len(p) and I[i] != p[j]:
            j += 1
            cnt += 1
        if j >= len(p):
            flag = 1
            print(f"Case #{_ + 1}: IMPOSSIBLE")
            break
        if I[i] == p[j]:
            j += 1
    if flag == 0:
        print(f"Case #{_ + 1}: {cnt + len(p) - j}")