AcWing 4382. 快速打字

原题链接：AcWing 4382. 快速打字
关键词：双指针、判断子序列

芭芭拉是一个速度打字员。

为了检查她的打字速度，她进行了一个速度测试。

测试内容是给定她一个字符串 I，她需要将字符串正确打出。

但是，芭芭拉作为一个速度打字员，在追求速度的同时，难免会发生一些错误，按错一些按键。

最终，芭芭拉打出的字符串为 P。

现在，芭芭拉想知道，能否仅通过删除一些额外字母的方式，将字符串 P 变为字符串 I。

如果可以，则输出需要删除的字母数量，如果不行，则输出 IMPOSSIBLE。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据占两行，第一行包含字符串 I，第二行包含字符串 P。

输出格式
每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x 为组别编号（从 1 开始），y 为需要删除的字母数量或 IMPOSSIBLE 。

数据范围

• 1≤T≤100,
• 字符串 I 和 P 均只包含大小写字母。
• 1≤|I|,|P|≤10⁵。

输入样例1：

2
aaaa
aaaaa
bbbbb
bbbbc

输出样例1：

Case #1: 1
Case #2: IMPOSSIBLE

输入样例2：

2
Ilovecoding
IIllovecoding
KickstartIsFun
kkickstartiisfun

输出样例2：

Case #1: 2
Case #2: IMPOSSIBLE

---

方法一：判断子序列

思路:

用两个指针i和j遍历两个字符串，如果相同便将i往后走，当i能走到头则说明字符串a是字符串b的子序列

C++ 实现：

#include <iostream>
#include <cstring>
using namespace std;const int maxn = 1e5 + 10;
int t, n, m;
char a[maxn], b[maxn];int main(){scanf("%d", &t);for(int cases = 1; cases <= t; cases ++ ){scanf("%s%s", a, b);int i = 0, j = 0, n = strlen(a), m = strlen(b);// 双指针 当i走完说明是a是b的子序列 反之说明不是while(i < n && j < m){if(a[i] == b[j])i++;j++;}printf("Case #%d: ", cases);if(i == n)printf("%d\n", m - n);elseputs("IMPOSSIBLE");}return 0;
}