103 扩展 KMP(Z 函数)

视频链接：

 P5410 【模板】扩展 KMP（Z 函数）

// P5410 【模板】扩展 KMP（Z 函数）
#include 
#include 
#include 

using namespace std;
const int N=2e7+5;
char a[N], b[N];
int z[N], ex[N];

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

// 计算 ex函数
void get_ex(char*a,int na,char*b,int nb){
  
  for(int i=1, l=0, r=0; i<=na; ++i){
    if(i<=r&&z[i-l+1]1) ex[i]=z[i-l+1];
    else{
      ex[i]=max(0, r-i+1);
      while(i+ex[i]<=na && 1+ex[i]<=nb
        && a[i+ex[i]]==b[1+ex[i]]) ++ex[i];
      l=i, r=i+ex[i]-1;
    }
  }
}

int main(){
    scanf("%s%s", a+1, b+1);
    int na=strlen(a+1), nb=strlen(b+1);
    get_z(b, nb);
    get_ex(a, na, b, nb);
    
    long long ans1 = 0, ans2 = 0;
    for(int i=1; i<=nb; ++i)
      ans1 ^= 1LL*i*(z[i]+1);
    for(int i=1; i<=na; ++i)
      ans2 ^= 1LL*i*(ex[i]+1);
    printf("%lld\n%lld\n",ans1,ans2);
    return 0;
}