zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

没想到kmp也可以这么秒

从n到1想一下

算出next数组之后可以直接递推

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
char str[N];
int len;
int nt[N];
int res[N];
void getNext(){
    nt[0] = -1;
    int i = 0, j = -1;
    while (i <= len){
        if (j == -1 || str[i] == str[j])
            nt[++i] = ++j;
        else
            j = nt[j];
    }
}

int main(){
    scanf("%s", str);
    len = (int)strlen(str);
    getNext();
    for (int i = len; i >= 1; i--){
        res[i]++;
        res[nt[i]] += res[i];
    }
    long long ans = 0;
    for (long long i = 1; i <= len; i++)
        ans = max(i * res[i], ans);
    printf("%lld\n", ans);
}
51nod 1277 字符串中的最大值
comment评论
Search
search