# 人物相关性分析

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

他想知道在小说中 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 同时出现的次数。

**数据范围**

```
1≤K≤1000000
```

**输入样例：**

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

**输出样例：**

```
2
```

以下选项<span style="color:red">错误</span>的是？

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```

### after

```cpp

```

## 答案

```cpp
int main()
{
    int k;
    scanf("%d", &k);
    getchar();

    const char *a = "Alice", *b = "Bob";
    char str[1000000];
    gets(str);

    int length = strlen(str);
    int num = 0, i, j, t, flag;
    char word[20];
    for (i = 0; i < length; i++)
    {
        if (str[i] == 'A' || str[i] == 'B')
        {
            j = 0;
            while (str[i] != ' ' && str[i] != '.')
                word[j++] = str[i++];
            word[j] = '\0';

            flag = 0;
            if (strcmp(word, a) == 0)
                flag = 1;
            else if (strcmp(word, b) == 0)
                flag = 2;

            if (flag == 1)
            {
                for (t = i; t < length; t++)
                {
                    if (str[t] == 'B')
                    {
                        j = 0;
                        while (str[t] != ' ' && str[t] != '.')
                            word[j++] = str[t++];
                        word[j] = '\0';

                        if (strcmp(word, b) == 0)
                            num++;
                    }
                }
            }
            else if (flag == 2)
            {
                for (t = i; t < length; t++)
                {
                    if (str[t] == 'A')
                    {
                        j = 0;
                        while (str[t] != ' ' && str[t] != '.')
                            word[j++] = str[t++];
                        word[j] = '\0';

                        if (strcmp(word, a) == 0)
                            num++;
                    }
                }
            }
        }
    }
    printf("%d\n", num);

    return 0;
}
```

## 选项

### A

```cpp
int cnt, k;
bool temp = true;
char f[2][20] = {"Alice", "Bob"};
bool check(string &a, int &pa, int &pb)
{
    bool flage = true;
    pa = a.find(f[0], ++pa);
    if (pa == -1)
        temp = false;
    if (temp && abs((pa - 1) - pb) < k && pb)
        cnt++;
    if (a[pa - 1] != ' ' && a[pa + 6] != ' ')
        flage = false;
    pb = a.find(f[1], ++pb);
    if (pb == -1)
        temp = false;
    if (a[pb - 1] != ' ' && a[pb + 6] != ' ')
        flage = false;
    return flage;
}
int main()
{
    string a;
    cin >> k;
    getchar();
    getline(cin, a);
    int pa = 0, pb = 0;
    while (1)
    {
        if (check(a, pa, pb) && abs(pa - pb) < k && temp)
        {
            cnt++;
        }
        else if (!temp)
            break;
    }
    cout << cnt;
    return 0;
}
```

### B

```cpp
#define mem(a, b) memset(a, b, sizeof a)
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define gcd(a, b) __gcd(a, b)
#define ft first
#define sd second
#define endl '\n'
#define PI acos(-1.0)
#define lcm(a, b) a / gcd(a, b) * b
#define INF_INT 0x3f3f3f3f
#define INF_LONG 4557430888798830399
const int N = 4e6 + 9;
int ta, tb;
int a[N], b[N];
string s;
int solve(string ss, int *cnt)
{
    int t = 0, n = s.size();
    for (int i = 0; i < n; i++)
    {
        if (s[i] == ss[0])
        {
            if (i)
            {
                char ch = s[i - 1];
                if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
                    continue;
            }
            int flag = 1, j;
            string tmp = "";
            for (j = i; j < n && j - i < ss.size(); j++)
            {
                tmp += s[j];
            }
            if (tmp != ss)
                flag = 0;

            if (j < n && ((s[j] >= 'a' && s[j] <= 'z') || (s[j] >= 'A' && s[j] <= 'Z')))
                flag = 0;
            if (flag)
                cnt[t++] = i;
        }
    }
    return t;
}
int main()
{
    int k;
    cin >> k;
    getchar();
    getline(cin, s);
    int ta = solve("Alice", a);
    int tb = solve("Bob", b);
    ll ans = 0;
    for (int i = 0, lp = 0, rp = 0; i < ta; i++)
    {
        while (b[lp] < a[i] - 3 - k)
            lp++;
        while (b[rp] <= a[i] + k + 5 && rp < tb)
            rp++;

        if (rp - lp > 0)
            ans += (ll)(rp - lp);
    }
    cout << ans << endl;
    return 0;
}
```

### C

```cpp
int len;
string s;
bool check(int i)
{
    if (len - i < 5)
        return false;
    return s[i + 1] == 'l' && s[i + 2] == 'i' && s[i + 3] == 'c' && s[i + 4] == 'e';
}
bool check2(int i)
{
    if (len - i < 3)
        return false;
    return s[i + 1] == 'o' && s[i + 2] == 'b';
}
int main()
{
    int k;
    cin >> k;
    getchar();
    getline(cin, s);
    len = s.length();
    vector<int> Alice, Bob;
    for (int i = 0; i < len; i++)
    {
        if (s[i] == 'A' && check(i))
        {
            Alice.push_back(i);
            i += 5;
        }
        else if (s[i] == 'B' && check2(i))
        {
            Bob.push_back(i);
            i += 3;
        }
    }
    int As = Alice.size(), Bs = Bob.size();
    int i = 0, j = 0;
    long long ans = 0;
    for (int q = 0; q < As; q++)
    {
        while (i < Bs && Bob[i] < Alice[q] - k - 3)
            i++;
        while (j < Bs && Bob[j] <= Alice[q] + k + 5)
            j++;
        ans += j - i;
    }
    cout << ans << "\n";
    return 0;
}
```