题目描述

题目描述

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

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

例如以下文本： 

ThisisastoryaboutAliceandBob.AlicewantstosendaprivatemessagetoBob. 

假设 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。 
第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超 过 1000000。

【输出格式】

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

【样例输入】 

20 

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

【样例输出】

2

【评测用例规模与约定】

对于所有评测用例，1≤ K ≤1000000。

时间限制：1.0s

内存限制：512.0MB

算法1

第一步：用两个数组保存分别找出Alice，Bob的首字母在字符串中位置
第二步：分别求出Alice前面的Bob个数 Bob前面Alice的个数 之和为Alice 和 Bob 同时出现的次数。

时间复杂度

O(n)

java 代码

import java.util.Scanner;


public class Main {

    static int[] a=new int[1000010];
    static int[] b=new int[1000010];

    public static boolean check(char str) {
        return (str>='A' && str<='Z' || str>='a' && str<='z');
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k=sc.nextInt();
        String s=sc.nextLine();
        s=sc.nextLine();

        //找Alice在字符串中第一个字母A的位置
        int x=0;    //Alice的个数
        for(int i=0;i+5<=s.length();i++) {
            if((i==0 || !check(s.charAt(i-1))) && (i+5==s.length() || !check(s.charAt(i+5)))) {
                if(s.substring(i, i+5).equals("Alice")) {                   
                    a[x++]=i;
                }
            }
        }
        //找Bob在字符串中第一个字母B的位置
        int y=0;    //Bob的个数
        for(int i=0;i+3<=s.length();i++) {
            if((i==0 || !check(s.charAt(i-1))) && (i+3==s.length() || !check(s.charAt(i+3)))) {
                if(s.substring(i, i+3).equals("Bob")) {
                    b[y++]=i;
                }

            }
        }

        long res=0;
        for(int i=0,l=0,r=-1;i<x;i++) {     //
            while(r+1<y && a[i]-1>=b[r+1]) {
                r++;        //Alice前面所有的Bob个数（r全集）
            }
            while(l<=r && (a[i]-1)-(b[l+1]+3)+1>k) {        //a[i]-1 表示Alice的前一个字母
                l++;        //Alice与Bob间距超过k的Bob个数（r的子集）
            }
            res+=r-l+1;     //Alice与Bob间距不大于k的Bob个数(r的子集)
        }

        for(int i=0,l=0,r=-1;i<y;i++) {
            while(r+1<x && b[i]-1>=a[r+1]) {
                r++;        //Bob前面所有的Alice个数r（全集）
            }
            while(l<=r && (b[i]-1)-(a[l+1]+5)+1>k) {        //a[i]-1 表示Alice的前一个字母
                l++;       //Alice与Bob间距超过k的Alice个数（r的子集）
            }
            res+=r-l+1;     //Alice与Bob间距超过k的Alice个数（r的子集）
        }
        System.out.println(res);
    }
}