笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「淼」CF126B Password

posted on 2020-05-20 08:09:14 | under 题解 |

发这个题解只是因为…大多数人的 Z 函数解法复杂度根本不对…

以下是这题用 Z 函数各种不对的复杂度做法:

1、枚举每一个后缀,通过 Z 可以求出与前缀的 LCP 然后去串里面暴力找子串。

2、枚举每一个中间串,通过 Z 可以求出与前缀的 LCP ,将这些长度暴力染色,遇到后缀就判一下。

……然后这两种复杂度都不对。考虑怎么优化一下。发现我们只关心最长能够匹配的前缀,因为前缀是固定的。于是记录一下这个最大值就好了。复杂度线性。


namespace Z_F{
    int L ;
    int Q ;
    int l, r ;
    int Z[N] ;
    int Pz[N] ;
    void gao(int bg, int L){
        for (int i = bg ; i < bg + L ; ++ i) Z[i] -- ;
        Z[bg] = L ;
    }
    int get_Z(char *s, int bg, int oo = 0){
        L = strlen(s + bg) ;
        l = bg, r = 0 ; Z[bg] = 0 ;
        for (int i = bg + 1 ; i < bg + L ; ++ i){
            if (r < i) Z[i] = 1 ;
            else Z[i] = min(Z[i - l + 1], r - i + 1) ;
            while (s[Z[i]] == s[i + Z[i] - 1]) ++ Z[i] ;
            if (r < i + Z[i] - 1) r = i + Z[i] - 1, l = i ;
        }
        if (!oo) gao(bg, L) ;
        return L ;
    }
    int exKMP(char *s, int bg, char *t, int gb){
        int q = get_Z(s, bg, 1) ; s[q + 1] = '#' ;
        L = strlen(t + gb) ; l = gb, r = 0 ;
        for (int i = gb ; i < gb + L ; ++ i){
            if (r < i) Pz[i] = 1 ;
            else Pz[i] = min(Z[i - l + 1], r - i + 1) ;
            while (s[Pz[i]] == t[i + Pz[i] - 1]) ++ Pz[i] ;
            if (r < i + Pz[i] - 1) r = i + Pz[i] - 1, l = i ;
        }
        for (int i = gb ; i < gb + L ; ++ i) Pz[i] -- ;
        return L ;
    }
}

int mx ;
int res ;
int Z1[N] ;
int Z2[N] ;
int tmp[N] ;
int ans[N] ;

int n, p ;
char s[N] ;
char t[N] ;

using namespace Z_F ;

int main(){
    scanf("%s", s + 1) ;
    n = get_Z(s, 1) ; res = 0 ;
    for (int i = 2 ; i <= n ; ++ i){
        if (i + Z[i] - 1 == n && Z[i] <= mx)
            if (res < Z[i]) res = Z[i], p = i ;
        chkmax(mx, Z[i]) ;
    }
    if (!res)
        return puts("Just a legend"), 0 ;
    for (int i = p ; i <= p + res - 1 ; ++ i)
        putchar(s[i]) ; return puts(""), 0 ;
}