蓝桥杯：人物相关性分析

news/2024/5/20 9:21:00 标签: 蓝桥杯, 滑动窗口

蓝桥杯：人物相关性分析https://www.lanqiao.cn/problems/198/learning/

目录

题目描述   

输入描述

输出描述

输入输出样例

输入

输出

输入

输出

运行限制

题目分析:(滑动窗口)

AC代码（JAVA）

题目描述   

        小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。

        更准确的说，小明定义 Alice 和 Bob "同时出现" 的意思是：在小说文本 中 Alice 和 Bob 之间不超过 K 个字符。

        例如以下文本：

This is a story about Alice and Bob.Alice wants to send a private message to Bob.

        假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是"Alice and Bob" 和 "Bob. Alice"。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。

注意:

  1. Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。

  2. Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能 有字母。例如出现了 Bobbi 并不算出现了 Bob。

输入描述

        第一行包含一个整数 K（1≤K≤10^{6}）。

        第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超过 10^{6}。

输出描述

输出一个整数，表示 Alice 和 Bob 同时出现的次数。

输入输出样例

输入

20
This is a story about Alice and Bob.Alice wants to send a private message to Bob.

输出

2

输入

1000
Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Alice.Bob.Bob.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Alice.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Bob.Bob.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Bob.Alice.Bob.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Bob.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Bob.Alice.Alice.Alice.Alice.Bob.Bob.Bob.Bob.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Bob.Bob.Alice.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Bob.Alice.Alice.Bob.Alice.Alice.

输出

191784

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 512M

题目分析:(滑动窗口)

        我们需要记录下每个Alice和Bob出现的下标，记录Alice和Bob这两个单词首字母出现的下标，方便后续进行操作，不然每次搜索Alice的时候都需要进行equals判断，耗时非常高的。

        遍历给定字符串str，我们分别记录下Alice和Bob出现的下标，分别存储到两个数组中，并且记录长度。

        判断出现的下标的时候，首先判断头部是A还是B，如果是A，那么就需要判断末尾是否位e，则判断后面第四位是不是e。

        B同理，同样需要判断末尾是不是b，也就是判断判断后面第二位是不是b。

        如果是了，就在进行字符串截取和比较，与Alice or Bob相同则记录到数组中。

        //记录Alice和Bob出现的下标
        for(int i = 0;i<len;i++) {
            //判断Alice首尾是否相同
            if(i+4 < len && str.charAt(i) == 'A' && str.charAt(i+4) == 'e') {
                //在截取判断
                if(str.substring(i,i+5).equals("Alice")) Alice[length++] = i;
            }
            //判断Bob首尾是否相同
            if(i+2 < len && str.charAt(i) == 'B' && str.charAt(i+2) == 'b') {
                //在截取判断
                if(str.substring(i,i+3).equals("Bob")) Bob[size++] = i;
            }
        }

             如果使用双重for循环来遍历Alice和Bob数组的话，肯定会有超时的，但也能拿80%。

        所以我们要对双重for进行优化，我们这里选择滑动窗口进行优化，下面是可行性分析：        

        如同所示，假设K=10，A，B数组存放Alice和Bob出现的下标，如图所示。

        那么，我们看一下哪个范围可以使A[0] = 10,与B[i]相差不超过10，

        [ A[0] - 10, A[0] + 10 ] 也就是说，如果处于这个范围之内，Alice和Bob是合法的。

        但是题目中是有限制的：

        如 "Alice and Bob" 之间有5个字符。

        如"Bob.Alice"之间有1个字符。

        也就是说，如果从Alice，往右边数的话，其实是要从Alice的e，到K个字符之间，都算合法距离。也就是说，Alice记录的是A出现的下标，但是从Alice往右边数是从e开始数的，所以实际计算记录应该要+4。

        同样，假如Bob在Alice左边，那么实际有效范围应该是从Bob的b到Alice的A，那么记录Bob出现的下标只记录了B，那么如果要从b开始，就要+上2，才算是Bob实际的出现次数。

        这里继续距离，当K=5，如果Alice[i] = 15，那么他的合法数据范围应该是 10-15,15-20。

        左边界10也就是Bob的b必须在的位置，右边界20必须是Bob的B所在的位置

         如此我们可以汇总得到范围为 [ Alice[i]-K-2,Alice[i]+K+4 ] 。

        也就是在[ Alice[i]-K-2,Alice[i]+K+4 ] 范围内的数据都是合法的，那么我们需要left和right，都在这个范围之外，这样就能保证right-left 就能得到这个区间内合法的数据

        也就是时刻要保证Bob[left] < Alice[i]-K-2, 并且 Alice[i]+K+4 < Bob[right].

        推导出公式，接下来是窗口的滑动问题，

        我们可以假设如果 Bob[left] == Alice[i]-k+2 并且 Alice[i]+k+4 == Bob[right]，

        那么Alice[i+1]必定大于Bob[left]+k+2,同时也大于Bob[right]+k+4，所以我们的窗口只需要跟着i进行滑动即可，也就是在第一次滑动之后每次根据Alice[i]的值进行滑动，避免重复计算，减少Bob数组的遍历。

AC代码（JAVA）

        代码中为了保证Bob[right] > Alice[i]+K+4,则每次当 Bob[right] < Alice[i]+K+5时，就让right右移。

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static int K;
    static String str;
    public static void init() {
        Scanner scan = new Scanner(System.in);
        K = scan.nextInt();
        scan.nextLine();
        str = scan.nextLine();
        scan.close();
    }

    static int[] Alice = new int[1000000];
    static int length = 0;
    static int[] Bob = new int[1000000];
    static int size = 0;
    public static void main(String[] args) {
        init();
        int len = str.length();

        //记录Alice出现的下标
        for(int i = 0;i<=len-5;i++) {
            //判断首尾是否相同
            if(str.charAt(i) == 'A' && str.charAt(i+4) == 'e') {
                //在截取判断
                if(str.substring(i,i+5).equals("Alice")) Alice[length++] = i;
            }
        }
        //记录Bob出现的下标
        for(int i = 0;i<=len-3;i++) {
            //判断首尾是否相同
            if(str.charAt(i) == 'B' && str.charAt(i+2) == 'b') {
                //截取判断
                if(str.substring(i,i+3).equals("Bob")) Bob[size++] = i;
            }
        }

        //以Alice进行遍历，那么在他的范围内，就是[Alice[i]-k,Alice[i]+k]
        //但是如果Bob在Alice的左边，那么需要算上o和b这两个字符，所以左边界应该是[Alice[i]-k+2
        //如果Bob在Alice右边，那么是从Alice的e开始计算到Bob的计算，那么右边界就是[Alice[i]+k+4
        long ans = 0;
        //这里可以推导，假设Bob[left] == Alice[i]-k+2 && Alice[i]+k+4 == Bob[right]
        //那么Alice[i+1]必定大于Bob[left]+k+2,同时也大于Bob[right]+k+4
        //因此双指针定义在循环外面，作为窗口，跟着i进行滑动
        int left = 0;
        int right = 0;
        for(int i = 0;i<length;i++) {
            //收缩左窗口
            while(left < size &&  Alice[i]-K-2 > Bob[left]) {
                left++;
            }
            //扩展右窗口,必须保证Bob[right]  > Alice[i]+K+4
            while(right < size && Alice[i]+K+5 > Bob[right]) {
                right++;
            }
            //当前位置的数量就是 右窗口-左窗口
            ans += Math.max((right-left),0);
        }

        System.out.println(ans);
    }
}


http://www.niftyadmin.cn/n/215326.html

相关文章

手拉手Centos7安装配置Redis7

手拉手Centos7安装配置Redis7

Redis&#xff08;Remote Dictionary Server )&#xff0c;即远程字典服务&#xff0c;是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;并提供多种语言的API。 Redis是一个NoSQL数据库&#xff0c;常用缓存(cache) Re…
阅读更多...
UE-Ueransim-5GC全链路开发记录

UE-Ueransim-5GC全链路开发记录

目录 1. 系统配置 1.1 Ueransim配置 1.2 UE配置 2. 启动 3. 实际演示 附录 代理1&#xff1a;ueransim-5gc 代理2 ue-ueransim TCPclient TCPserver 1. 系统配置 1.1 Ueransim配置 ueransim的yaml文件如下 version: 3.8 services:ueransim2:container_name: uera…
阅读更多...
Spring注入方式：@Autowired和@Resource的区别和应用场景

Spring注入方式：@Autowired和@Resource的区别和应用场景

Resource和Autowired是Spring Framework中两种常用的注入方式,它们的作用是在Spring容器中自动装配Bean对象. Autowired Autowired是Spring Framework提供的注解,它也可以实现自动装配Bean对象. RestController public class DemoController {/*** 下面两种Autowired使用一种…
阅读更多...
刷题_34：收件人列表 and 养兔子

刷题_34：收件人列表 and 养兔子

一.收件人列表 题目链接&#xff1a; 收件人列表 题目描述&#xff1a; NowCoder每天要给许多客户写电子邮件。正如你所知&#xff0c;如果一封邮件中包含多个收件人&#xff0c;收件人姓名之间会用一个逗号和空格隔开&#xff1b;如果收件人姓名也包含空格或逗号&#xff0c;…
阅读更多...
清明-微信小程序

清明-微信小程序

# 云开发接入 初始化云开发 环境保密
阅读更多...
3.14、信号量

3.14、信号量

3.14、信号量1.信号量的介绍2.信号量的相关函数3.信号量函数的使用介绍4.用信号量实现生产者消费者模型1.信号量的介绍 信号量则是一种计数器&#xff0c;可以用来同步多个线程之间的操作。当线程需要访问某个受保护的资源时&#xff0c;它需要先获取信号量。如果信号量的值大于…
阅读更多...
基于html+css的盒子展示2

基于html+css的盒子展示2

准备项目 项目开发工具 Visual Studio Code 1.44.2 版本: 1.44.2 提交: ff915844119ce9485abfe8aa9076ec76b5300ddd 日期: 2020-04-16T16:36:23.138Z Electron: 7.1.11 Chrome: 78.0.3904.130 Node.js: 12.8.1 V8: 7.8.279.23-electron.0 OS: Windows_NT x64 10.0.19044 项目…
阅读更多...
fastDDS之Subscriber

fastDDS之Subscriber

订阅由定义了DataReader与Subscriber的关联。为了接收发布的消息&#xff0c;应用程序需要再Subscriber创建一个新的DataReader。这个DataReader将被绑定到描述将要接收的数据类型的Topic上&#xff0c;然后就开始开始从与此Topic匹配的Publisher接收数据。 当Subscriber接收到…
阅读更多...
最新文章

Copyright @ 2022~2023