Z函数——拓展KMP

算法作用：(考虑1base)求文本串 T 的每一个后缀与模式串 M 的最长公共前缀长度。核心数组z[i]就表示lcp(s[i:end],s[1:n])lcp(s[i:end],s[1:n])

模板：

1.传的是0base串，函数内部会处理。

2.其次一般来说前面是模式串，间隔一个$分隔符后是文本串。这样就是可以知道文本串中出现了多少次模式串。

z函数的求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> exkmp(string s){
    int len=s.size();
    s=" "+s;
    vector<int> z(len+1);
    
    z[1]=0;
    int l=1,r=0;
    for(int i=2;i<=len;i++){
        if(i>r)z[i]=0;
        else {//利用之前的信息
            int k=i-l+1;
            z[i]=min(z[k],r-i+1);
        }
        while(i+z[i]<=len&&s[z[i]+1]==s[i+z[i]])z[i]++;
        if(i+z[i]-1>r){
            l=i;r=i+z[i]-1;
        }
    }
    return z;
}

如何达到kmp的匹配作用（无关border）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve()
{
    // p为模式串，s为匹配串
    string p, s;
    cin >> n >> p >> m >> s;
    p += "$" + s;
    auto z = exkmp(p);
    // for(int i=1;i<=n;i++)cerr<<z[i]<<" ";
    for (int i = n + 2; i <= n + m + 1; i++)
    {
        if (z[i] == n)
        {
            cout << i - (n + 2) << " ";
        }
    }
}

例题1：给定字符串S，求最长子串T满足：T是S的前缀又是 𝑆的后缀同时又在 𝑆中间出现过。Password - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Sol：如何用exkmp解决？考虑首先需要满足lcp长度是正好能到后缀的，这用z函数很好约束。考虑怎么处理在中间出现过这个问题？考虑维护最大z[i]值为x,对于当前这个位置的z[i],满足x<=z[i]即可，这是由于z[i]具有二段性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve()
{
    string s;cin >> s;
    n = s.size();
    auto z = exkmp(s);
    s = " " + s;
    int x = 0;int res = 0;int pos = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i + z[i] - 1 == n && x >= z[i])
        {
            if (z[i] > res)
            {
                res = z[i];
                pos = i;
            }
        }
        x = max(x, z[i]);
    }
    if (res)
        cout << s.substr(pos, res);
    else
        cout << "Just a legend" << endl;
}

bonus:如何用kmp解决？

答案一定是某个前缀，我们只需要知道长度就可以了。由于是前缀也是后缀，所以考虑border。而不难画图发现答案一定为nx[nx[n]]或者nx[n]。按长度从大到小依次判断出现次数即可。

void solve(){
       string s;
       cin>>s;
       KMP kmp(s);
       auto v=kmp.getnxt();
       int n=s.size();
       s=" "+s;
       map<int,int>mp;
       for(int i=1;i<=n;i++){
                  mp[v[i]]++;
       }
       int len=0;
       if(mp[v[n]]>=2)len=v[n];
       else len=v[v[n]];
       if(len)cout<<s.substr(1,len)<<endl;
       else  cout<<"Just a legend"<<endl;
}