Z函数（扩展kmp）

BB

还好qhd没考Z函数，要不然人都没了 QAQ

 

Introduction

Z函数，国内称为 扩展kmp，可以在O(n)时间内求得所有的i(i>1)，lcp(s[i...len], s[1...len])

 

Password - CodeForces 126B

Description
给定串s (|s| <= 1e6)，在此串中找出一个最长串t，使其既作为前缀出现，又作为后缀出现，同时在中间出现
Sample Input

fixprefixsuffix
abcdabc

Sample Output

fix
Just a legend

Solution - Z函数
首先跑Z函数后，把既是前缀又是后缀的长度放入set中
然后再次遍历这一字符串，如果对于某一位置i，若i+z[i]-1==n那么说明这一串是后缀，为了在中间出现，取m=z[i]-1，否则取m=z[i]，这里的m就是这一位置作为中间串出现的可能的最长长度。在set中找到不超过m的最大值，即是这一位置作为前缀和后缀，又在中间出现的串的最大值。遍历每一个位置，更新最大值及其位置即可

#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6 + 15;
typedef long long ll;

char s[N];
int z[N];
int arr[N];

inline void zFunc(char* s, int n) {
    z[1] = 0;
    for(int i = 2, l = 1, r = 1; i <= n; i++) {
        z[i] = 0;
        if(i <= r) {
            z[i] = min(z[i - l + 1], r - i + 1);
        }
        while(i + z[i] <= n && s[1 + z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
}

int main() {
  while(~scanf("%s", s + 1)) {
        int n = strlen(s + 1);
        zFunc(s, n);

        int k = 0;
        for(int i = 2; i <= n; i++) {
            if(i + z[i] - 1 == n) {
                arr[++k] = z[i];
            }
        }
        sort(arr + 1, arr + 1 + k);

        int ans = -1, pos = -1;
        for(int i = 2; i <= n; i++) {
            int m = z[i] - (i + z[i] - 1 == n);
            auto it = upper_bound(arr + 1, arr + 1 + k, m);
            if(it != arr + 1) {
                it--;
                if(ans < *it) {
                    ans = *it;
                    pos = i;
                }
            }
        }
        if(pos != -1) {
            printf("%.*s\n", ans, s + pos);
        } else {
            puts("Just a legend");
        }
  }
}

 

Prefixes and Suffixes - Codeforces 432D

Description
给定串s (|s| <= 1e5)，给出所有即作为前缀又作为后缀出现的串的出现次数
Sample Input

ABACABA
AAA

Sample Output

3
1 4
3 2
7 1
3
1 3
2 2
3 1

Solution - Z函数
跑完z函数后（建议z[1]=n，方便处理），把z[i]全部插入数组中。此后，对于每一个位置，数组中大于等于z[i]的数量即为出现次数

#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6 + 15;
typedef pair<int, int> pii;
typedef long long ll;

char s[N];
int z[N];
int arr[N];

inline void zFunc(char* s, int n) {
    z[1] = n;
    for(int i = 2, l = 1, r = 1; i <= n; i++) {
        z[i] = 0;
        if(i <= r) {
            z[i] = min(z[i - l + 1], r - i + 1);
        }
        while(i + z[i] <= n && s[1 + z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
}

int main() {
  while(~scanf("%s", s + 1)) {
        int n = strlen(s + 1);
        zFunc(s, n);

        for(int i = 1; i <= n; i++) {
            arr[i] = z[i];
        }
        sort(arr + 1, arr + 1 + n);

        vector<pii> vec;
        for(int i = n, j = 1; i >= 1; i--, j++) {
            if(i + z[i] - 1 == n) {
                int cnt = arr + 1 + n - lower_bound(arr + 1, arr + 1 + n, z[i]);
                vec.push_back(make_pair(j, cnt));
            }
        }

        printf("%d\n", (int)vec.size());
        for(const pii& pr : vec) {
            printf("%d %d\n", pr.first, pr.second);
        }
    }
}

 

string matching - HDU 6629

Sample Input

3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc

Sample Output

17
7
32

Solution 1 - kmp的next数组
实际上，只需要计算next数组，然后提前统计嵌套下的次数（类似前缀和），最后累加该值即是答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e6 + 15;
const int inf = 0x3f3f3f3f;

char s[N];
int knxt[N], kcnt[N];

void getNext(char* p) {
    knxt[0] = -1;
    kcnt[0] = 1;
    int k = -1, j = 0;
    while(p[j]) {
        if(k == -1 || p[k] == p[j]) {
            j++;
            k++;
            //knxt[j] = (p[k] != p[j] ? k : knxt[k]);
            knxt[j] = k;
            kcnt[j] = kcnt[k] + 1;
        } else {
            k = knxt[k];
        }
    }
}

ll solve(char* s) {
    getNext(s);
    ll ans = 0;
    for(int i = 0; s[i]; i++) {
        ans += kcnt[i];
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        printf("%lld\n", solve(s) - strlen(s));
    }
}

Solution 2 - Z函数
然而，这不是一道Z函数裸题嘛QAQ

#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6 + 15;
typedef long long ll;

char s[N];
int z[N];
int arr[N];

inline void zFunc(char* s, int n) {
    z[1] = 0;
    for(int i = 2, l = 1, r = 1; i <= n; i++) {
        z[i] = 0;
        if(i <= r) {
            z[i] = min(z[i - l + 1], r - i + 1);
        }
        while(i + z[i] <= n && s[1 + z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
	while(t--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        zFunc(s, n);

        ll ans = 0;
        for(int i = 2; i <= n; i++) {
            ans += 1 + z[i] - (i + z[i] - 1 == n);
        }
        printf("%lld\n", ans);
	}
}