[数据结构与算法]7-10 好前缀 (10 分) 二分答案+字符串处理

一、题目

我们称一个字符串的前缀为好前缀，如果它满足如下条件：

（1）它在字符串中至少出现2次；

（2）满足条件（1）的最长者。

请编写程序计算一个字符串的好前缀长度，注意一个字符串不能称为自己的前缀。

输入格式:

输入为一个字符串，包含不超过105个字母。

输出格式:

输出为一个整数，表示输入字符串的好前缀长度。

输入样例1:

abcabce

输出样例1:

3

输入样例2:

ababaxxy

输出样例2:

3

二、分析

设答案为y，长度大于y的前缀肯定不是好前缀（要不然y就是这个大于y的数了），长度小于y的前缀肯定也是好前缀。

所以答案具有二分性，可以使用二分求得答案。

字符串处理需要了解string和find函数。

三、代码

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

string str;

bool f(int mid)
{
    string op = string(str, 0, mid);
    int x = str.find(op);
    x = str.find(op, x + 1);
    return x != -1;
}

int main()
{
    cin >> str;

    int l = 1, r = str.size();
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (f(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << endl;
    return 0;
}