人物相关性分析C++_c++【问题描述】 小明正在分析一本小说中的人物相关性。他想知道在小说中 alice

小明正在分析一本小说中的人物相关性。

他想知道在小说中 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 个字符。

注意:

Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。
Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能有字母。例如 Bobbi 並不算出现了 Bob。
输入格式
第一行包含一个整数 K。

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

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

数据范围
1≤K≤1000000
输入样例：
20
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
输出样例：
2

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1000010;
vector<int> Alice,Bob;
int k;
string s;
int main()
{
    cin >> k;
    cin.get(); // 接受空字符
    getline(cin,s); 
    s += '.'; //最后一个可能不是字符，需加上；如：****Alice
    string temp = "";
    for (int i = 0 ; i < s.size() ; i ++)
    {
        
        if (!isalpha(s[i])) //如果s[i]不是一个字母，那么s[i-1]之前的就是一个单词
        {
            if(temp == "Alice")  Alice.push_back(i - temp.size() );
            else if(temp == "Bob") Bob.push_back(i - temp.size() );
            temp = "";
        }
        else temp += s[i];
    }
    int lp = 0 , rp = 0;
    long long ans = 0;
    int la = Alice.size();
    int lb = Bob.size();
    for (int i = 0 ; i < la ; i ++)
    {
        while (lp < lb &&Bob[lp] < Alice[i] - 3 - k) lp ++;
        while (rp < lb &&Bob[rp] <= Alice[i] + 5 + k) rp ++;
        if (rp - lp > 0) ans += rp - lp;
    }
    cout << ans << endl;
    return 0;
    
}
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
40
41