Codeforces 126B Password（Z-Box or kmp）

旧城等待， 2021-10-18 09:26 140阅读 0赞

## 题意：你要在一个串中找到“密码”，密码定义为既是前缀，也是后缀，同时在串中间出现过的子串。 ##

## 分析：字符串匹配经典题，用kmp肯定是可以的，但是最近学了一下Z-Box算法，就练一下，感觉比kmp更好理解，更实用。先预处理处z数组，如何保证前缀也是后缀呢?z\[i\]==n-i。直观理解上就是以这一位为开始的串有n-i位与前缀相同。就是后缀和前缀相等。那如何保证这一个串在中间也出现过呢？遍历的过程中记录一个z\[i\]的最大值maxx，若这个maxx>=n-i，则说明前面至少出现过不短于他的一个和前缀相同的串。画个草图更好理解。参考[https://blog.csdn.net/szh\_0808/article/details/79257961][https_blog.csdn.net_szh_0808_article_details_79257961]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+5;
    char s[N];
    int z[N],n;
    ///z数组模板函数
    void get_z()
    {
        int l=0,r=0;
        for (int i=1;i<n;i++)
        {
            if (i>r)
            {
                l=i,r=i;
                while (r<n && s[r-l]==s[r]) r++;
                z[i]=r-l,r--;
            }
            else
            {
                int k=i-l;
                if (z[k]<r-i+1) z[i]=z[k];
                else
                {
                    l=i;
                    while (r<n && s[r-l]==s[r]) r++;
                    z[i]=r-l,r--;
                }
            }
        }
    }
    
    int main()
    {
        scanf("%s",s);
        n=strlen(s);
        get_z();
        int maxx=0,pos=0;
        for (int i=1;i<n;i++)
        {
            if (z[i]==n-i && maxx>=n-i)
            {
                pos=i;
                break;
            }
            maxx=max(maxx,z[i]);
        }
        if (!pos) printf("Just a legend");
        else for (int i=0;i<n-pos;i++) printf("%c",s[i]);
        return 0;
    }

[https_blog.csdn.net_szh_0808_article_details_79257961]: https://blog.csdn.net/szh_0808/article/details/79257961