Skip to content

牛客网 NC207429 最大值#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: C/C++ 1秒，其他语言2秒

Memory Limit: C/C++ 262144K，其他语言524288K

1.2. Problem Description#

有一个字符串 ，对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。

请问给出一个字符串他的ac串最大长度为多少。

1.3. Input#

输入数据第一行是 ，表示数据的组数，接下来每组数据输入一个字符串 。

1.4. Output#

输出最大长度

1.5. Sample Input#

2
aaaaa
abacc

1.6. Sample Output#

4
1

1.7. Note#

aaaab的ac串是aaa(2:4)

acac的ac串是ac(3:4)

1.8. Source#

牛客网 NC207429 最大值

2. 解读#

我们有了一个输入字符串 ，设其非前缀子串为 ， ，其中 为字符串 的长度， 为左闭右开区间。这道题目想要求的是最大长度的非前缀子串 ，满足 。

这恰好就类似于 KMP算法 中 数组 的定义。

其中 表示我们要判断的是字符串 的长度为 的子串 ， 表示 的前 个字符组成的子串与后 个字符组成的非前缀子串相等，即

例如 aaaab 的 数组为 ，题目要求的ac串就是 数组中的最大值对应的字符串，也就是aaa。

推荐一个 KMP算法的可视化网站，里面还有各种算法的可视化，可以帮助理解。

3. 代码#

#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 1e5 + 1;

int Next[MAXN] = { 0 };

int getNext(string p, int length)
{
    Next[0] = 0;
    Next[1] = 0;
    for (int i = 1; i < length; i++) {
        int j = Next[i];
        while (j && p[i] != p[j]) {
            j = Next[j];
        }
        Next[i + 1] = (p[i] == p[j]) ? j + 1 : 0;
    }
    return 0;
}

int main()
{
    int t, maxN;
    string str;
    cin >> t;
    while (t--) {
        cin >> str;
        maxN = 0;
        getNext(str, str.size());
        for (size_t i = 1; i <= str.size(); i++) {
            maxN = max(Next[i], maxN);
        }
        cout << maxN << endl;
    }
}

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。

二维码

Back to top