51NOD 1277 字符串中的最大值（KMP）

》》点击进入原题测试《《

思路：用KMP优化的暴力写了一遍，超时！没有充分利用KMP中next数组的性质。

首先这个题是肯定要用到KMP算法的，然后会有一个next[]数组。

用一个数组来sum[i]表示长度为i的前缀的字符串有多少个，于是默认所有初始值为1；

然后倒着递推sum[next[i]]+=sum[i];原理的话自己找个样例手动模拟一下应该就清楚了，真的是很神奇的一个规律。

注意使用长整形，有个样例会溢出！

参照一下帖子 https://blog.****.net/largecub233/article/details/62039957

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int ne[];
void cal_next(string str)
{
    ne[] = -;
    int k = -;
    for (int i = ; i < str.length(); i++){
        while (k != - && str[k + ] != str[i])
            k = ne[k];

        if (str[k + ] == str[i])k += ;
        ne[i] = k;
    }
}
int kmp(string str, string str2)
{
    int k = -, sum = ;

    for (int i = ; i < str.length(); i++){
        while (k>- && str[k + ] != str[i])
            k = ne[k];
        if (str[k + ] == str[i])
            k += ;
        if (k == str2.length() - ){
            sum++;
            i -= ne[k] + ;
            k = -;
        }
    }
    return sum;
}
int main()
{
    string a; cin >> a;
    int maxs = ;
    cal_next(a);
    for (int i = ; i <= a.length(); i++){
        string temp = a.substr(, i);
        int ans = kmp(a, temp);
    //    cout << temp.length() << " " << ans << endl;
        if (ans*temp.length() > maxs)
            maxs = ans*temp.length();
    }
    cout << maxs << endl;
    return ;
}

暴力超时代码

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define  ll long long
ll ne[], sum[];
void cal_next(string str)
{
    ne[] = -;
    int k = -;
    for (int i = ; i < str.length(); i++){
        while (k != - && str[k + ] != str[i])
            k = ne[k];

        if (str[k + ] == str[i])k += ;
        ne[i] = k;
    }
}
int kmp(string str, string str2)
{
    int k = -, sum = ;

    for (int i = ; i < str.length(); i++){
        while (k>- && str[k + ] != str[i])
            k = ne[k];
        if (str[k + ] == str[i])
            k += ;
        if (k == str2.length() - ){
            sum++;
            i -= ne[k] + ;
            k = -;
        }
    }
    return sum;
}
int main()
{
    string a; cin >> a;
    ll maxs = ;
    for (int i = ; i <= a.length(); i++)
        sum[i] = ;

    cal_next(a);
    for (int i = a.length() - ; i >=; i--){
        maxs = max(maxs,(i+)*sum[i+]);
        sum[ne[i]+] += sum[i+];
    }
    cout << maxs << endl;
    return ;
}