题目链接
题目解法
很 \(nb\) 的字符串题
首先，\(x+y\) 是 \(s,t\) 的公共前缀，\(y+z\) 是 \(s,t\) 的后缀
所以如果 \(s,t\) 的最长公共后缀与 \(lcp\) 不交，那么无解，如果有解，则只留下 \(s,t\) 的最长公共后缀，因为前缀的不属于最长公共后缀的部分一定属于 \(x\)
所以现在的问题是：有串 \(s,t\)，且 \(s\) 是 \(t\) 的后缀，要求和原题一样的问题
因为 \(n<m\)，所以 \(x\) 是 \(y'+y^q\)，其中 \(y'\) 是 \(y\) 的后缀
考虑枚举 \(|y|\)
因为 \(x,z\) 的长度可以相抵，所以 \(|y^k|=|y|+m-n\)，但我们可以发现，\(|y^k|\) 可以在一个固定的范围内滑动，且后缀是无限制的（因为已经保证了 \(s\) 是 \(t\) 的后缀），只有右端点有 \(\le ?\) 的限制
考虑求出 \(?\)
手玩一下可以发现，\(|x+y^k|\le |y|+z_{|y|+1}\)，其中 \(z_i\) 表示 \(z\) 函数，是 \([i,len]\) 与 \([1,len]\) 的 \(lcp\)
这样可以发现，\(y^k\) 长度为 \(|y|+m-n\)，且最右边为 \(|y|+z_{|y|+1}\)，不难计算合法的 \(y^k\) 个数
时间复杂度 \(O(n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=10000100;
int n,m,z[N];
char s[N],t[N];
void Z_algo(){
z[1]=m;
for(int i=2,l=1,r=1;i<=m;i++){
if(i<=r) z[i]=min(z[i-l+1],r-i+1);
while(i+z[i]<=m&&t[i+z[i]]==t[z[i]+1]) z[i]++;
if(i+z[i]-1>r) r=i+z[i]-1,l=i;
}
}
int main(){
n=read(),m=read();
scanf("%s",s+1),scanf("%s",t+1);
int j=0;
while(j<n&&s[n-j]==t[m-j]) j++;
j=n-j;
F(i,1,j) if(s[i]!=t[i]){ puts("0");exit(0);}
F(i,j+1,n) s[i-j]=s[i];
F(i,j+1,m) t[i-j]=t[i];
n-=j,m-=j;
Z_algo();
LL ans=0;
F(i,1,m) if((m-n)%i==0){
int rb=i+z[i+1],leny=i+m-n;
ans+=max(0,rb-leny+1);
}
printf("%lld\n",ans);
return 0;
}