企业网站建设策划书1万字,福建泉州网站建设公司,个人做跨境电商怎么开始,长春网站制作方案定制原题链接#xff1a;AcWing 4382. 快速打字 关键词#xff1a;双指针、判断子序列
芭芭拉是一个速度打字员。
为了检查她的打字速度#xff0c;她进行了一个速度测试。
测试内容是给定她一个字符串 I#xff0c;她需要将字符串正确打出。
但是#xff0c;芭芭拉作为一…原题链接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|≤105。
输入样例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;
}
