扩展KMP算法

Z函数：

• 符串S的Z函数定义：\(\color{#50F}{z[i]为S与S_{(i , n) }的LCP(最长公共前后缀)}\)

Z函数的线性算法：

• 该算法如同大多数字符串算法，其关键在于，运用自动机的思想寻找限制条件下的状态转移函数，使得可以借助之前的状态来加速计算新的状态。

  对于\(\color{#51F}{ l}\) , 我们称\(\color{#51F}{[l ,l + z[l] - 1]}\)是\(\color{#51F}{ l}\) 的匹配段 ，及\(\color{#51F}{X-Box}\) ， 由定义可知\(\color{#51F}{字符串S_{(1 , z[l] - 1) }和字符串S_{( l , l + z[l] - 1)}}\)是相等所以在\(\color{#51F}{X-Box}\) 中枚举 \(\color{#51F}{ i}\) 对于每一个 \(\color{#51F}{ i}\) 我们都能在前缀串中找到对应的位置 \(\color{#51F}{ 1 + i - l }\) ，定义 \(\color{#51F}{X}\) 为 \(\color{#51F}{i+ z[1 + i - l] - 1}\) ， \(\color{#51F}{R}\)为 \(\color{#51F}{l + z[l] - 1}\)

  • 若 \(\color{#51F}{X< R}\) ：\(\color{#51F}{z[i] = z[l + i - l]}\)
  • 若\(\color{#51F}{X >= R}\) ：暴力枚举找出答案

  因为每次用\(\color{#51F}{R}\)最大的盒子，如果 \(\color{#51F}{i + z[i] -i}\) 大于\(\color{#51F}{R}\) 更新\(\color{#51F}{R}\) 的值

• 时间复杂度分析：\(\color{#51F}{X< R}\) ：\(每次o(1)的复杂度即可\) ， \(\color{#51F}{X >= R}\) 因为\(\color{#51F}{R}\) 的范围有限，枚举的次数总共为\(o(n)\)

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

P5410 【模板】扩展 KMP/exKMP（Z 函数） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include "bits/stdc++.h"
using namespace std ;
#define int long long
#define ull unsigned int
const int N = 1e6 + 9 ;
int p[N] , z[N] ;
char a[N] , b[N] ;
void get_z( char* s , int n ,int *z ) {
    z[1] = n ;
    for( int i = 2 , l = 0 , r = 0; i <= n ;i ++ ) {
        if( i <= r ) z[i] = min( r- i + 1 , z[ i - l + 1] ) ;
        while( i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) z[i] ++ ;
        if( i + z[i] -1 > r ) l = i , r = i + z[i] - 1 ;
    }
}
void get_p( char* s , char *t , int n , int  m, int *p ) { // s 的后缀与 t的最大前缀
    for( int i = 1 , l = 0 , r = 0 ; i <= n ; i ++ ) {
        if( i <= r ) p[i] = min( r - i + 1 , z[i - l + 1]);
        while( i + p[i] <= n &&1 + p[i] <= m && s[i + p[i]] == t[1 + p[i]] ) p[i] ++ ;
        if( i + p[i] - 1 > r ) 
            l = i , r = i + p[i] - 1 ;
    }
}
void solve( ) {
    int n , m ;
    cin >> a + 1 >> b + 1 ;
    n = strlen(a + 1) , m = strlen(b + 1) ;
    get_z( b , m , z ) ;
    get_p( a , b , n , m , p ) ;
    for( int i = 1 ; i <= n ; i ++ ) p[0] ^= i * (p[i] + 1);
    for( int i = 1 ; i <= m ;i ++ ) z[0] ^=  i * (z[i] + 1);
    cout << z[0] <<'\n' << p[0]<< '\n';
} 


signed main( ) {
    ios::sync_with_stdio(false) ,cin.tie(0) ,cout.tie(0) ;
    int _ = 1  ;
    while( _ --  ) {
        solve() ;
    }
}

F-不是烤串故事_牛客周赛 Round 56 (nowcoder.com)

#include "bits/stdc++.h"
using namespace std ;
const int N = 1e6 + 9 , inf = 0xc0c0c0c0c0c0c0c0;
string s1 , s2 , rs1 ;
vector<int> get_z( string s ) {
    int n = s.size() ;
    vector<int> z(n) ;
    z[0] = s.size() ;
    for( int i = 1 , l = 0 , r =0 ; i < s.size() ; i ++ ) {
        if( i <= r ) z[i] = min( r - i + 1 , z[i - l ] ) ;
        while( i + z[i] < n  && s[i + z[i]] == s[z[i]]) 
            z[i] ++ ;
        if( i + z[i] - 1 > r ) l = i , r = i + z[i] - 1 ; 
    }
    return z ;
}
vector<int> get_p( string s , string t , vector<int>& z ) {
    int n = s.size() ;
    vector<int> p(n) ;
    for( int i = 0 , l = 0 , r = -1 ; i < s.size() ; i ++ ) {
        if( i <= r ) p[i] = min( r - i + 1 , z[i - l ] ) ;
        while( i + p[i] < n  && s[i + p[i]] == t[ p[i]]) p[i] ++ ;
        if( i + p[i] - 1 > r ) l = i , r = i + p[i] - 1 ; 
    }
    return p ;
}
vector<int> get_x( string s , string t ) {
    int n = s.size() ;
    vector<int> x(n) ;
    for( int i = 0 , l = 0 , r =-1 ; i < s.size() ; i ++ ) {
        if( i <= r ) x[i] = r - i + 1;
        while( i + x[i] < n  && s[i + x[i]] == t[i + x[i]]) x[i] ++ ;
        if( i + x[i] - 1 > r ) l = i , r = i + x[i] - 1 ; 
    }
    return x ;
}
int n ;
void solve( ) {
    cin >> n ;
    cin >> s1 >> s2;
    vector<int> z = get_z(s2) ;
    reverse(s1.begin() ,s1.end()) ;
    vector<int> p = get_p(s1 , s2 , z ) ;
    reverse(s1.begin() ,s1.end()) ;
    vector<int> x = get_x(s1 , s2 ) ;
    int ma = -1 , ans ;
    for( int i = 0 ; i < n ;i ++ ) {
        int cnt = p[n - i - 1] ;
        if( cnt == i + 1 && i != n - 1 ) cnt += x[i + 1] ;
        if( ma < cnt ) ma = cnt , ans = i + 1 ;
    }
    cout << ma <<' ' << ans << '\n' ;
}

signed main() {
    ios::sync_with_stdio(false) , cin.tie(0) ,cout.tie(0) ;
    int _ = 1 ;
    cin >> _ ;
    while( _ -- ) {
        solve( ) ;
    } 
}