蓝桥杯-人物相关性分析

试题 H: 人物相关性分析
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
【问题描述】
小明正在分析一本小说中的人物相关性。他想知道在小说中 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。
第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超
过 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。
 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String arr=sc.nextLine();
		int k=Integer.valueOf(arr);
		String str=sc.nextLine();
		int count=0;
		List<Integer> a=fangfa(str,"Alice");
		List<Integer> b=fangfa(str,"Bob");
		
		for (int i = 0; i < a.size(); i++) {
			int aa=a.get(i);
			for (int j = 0; j <b.size(); j++) {
				int bb=b.get(i);
				int cc=aa-bb;
				if(cc>=-k-5&&cc<=k+3) {
					count++;
				}

			}
		}
		System.out.println(count);
	}
	public static boolean isChar(char c) {
		if(c>=97&&c<=122) {
			return true;
		}
		if(c>=65&&c<=90) {
			return true;
		}
		return false;
	}
	// 查找 出现的下标name
	private static List<Integer> fangfa(String str, String name) {
		// TODO Auto-generated method stub
		int a=str.indexOf(name);
		List<Integer> list=new ArrayList<Integer>();
		while (a!=-1) {
			char zuo=str.charAt(a-1);
			char you=str.charAt(a+name.length());
			if(isChar(zuo)||isChar(you)) {
			}
			else {
				list.add(a);
				a=str.indexOf(name,a+1);
			}
		}
		
		return list;
	}
}