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
2
3
4
5

• 输出样例1：

Case #1: 1
Case #2: IMPOSSIBLE
1
2

• 输入样例2：

2
Ilovecoding
IIllovecoding
KickstartIsFun
kkickstartiisfun
1
2
3
4
5

• 输出样例2：

Case #1: 2
Case #2: IMPOSSIBLE
1
2

题解

import java.util.Scanner;

/**
 * @author akuya
 * @create 2023-10-04-18:56
 */
public class Main {
    static int T=100;
    static int t;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        t=scanner.nextInt();
        int tt=t;
        while(t--!=0){
            String a=scanner.next();
            String b=scanner.next();
            int lena=a.length();
            int lenb=b.length();
            int p=0;
            for(int i=0;i<lenb;i++){
                if(b.charAt(i)==a.charAt(p)){
                    p++;
                }
                if(p==lena){
                    break;
                }
            }
            System.out.print("Case #");
            System.out.print(tt-t+": ");
            if(p==lena){
                System.out.println(lenb-lena);
            }else
            System.out.println("IMPOSSIBLE");

        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

思路

双指针的简单运用，两个字符串分别启用一个指针，通过双指针查找目标串是否有原始串的字母，存在用字符串长度相减即可，不存在输出impossible。