0pts求调,马蜂良好
查看原帖
0pts求调,马蜂良好
1396080
yh2023zlh楼主2025/7/3 21:37
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=6e6+7;
int n,m,dp[N],nxt[N],len,ans;
ll a[N];
string s,t,s_;
void manacher(){
	int mx=0,d=0;
	for(int i=1;i<s.size();i++){
		if(i<=mx){
			dp[i]=dp[2*d-i];
			if(i+dp[i]<=mx){
				continue;
			}
			while(i>dp[i]&&i+dp[i]+1<s.size()&&s[i+dp[i]+1]==s[i-dp[i]-1]) dp[i]++;
			if(i+dp[i]>mx) mx=dp[i]+i,d=i;
		}
		else{
			d=i;
			while(i>dp[i]&&i+dp[i]+1<s.size()&&s[i+dp[i]+1]==s[i-dp[i]-1]) dp[i]++;
			mx=dp[i]+i;
		}
	}
}
void kmp(){
	int i=1,j=0;
	while(i<s_.size()){
		if(s_[i]==s_[j]) nxt[i++]=++j;
		else if(j==0) i++;
		else j=nxt[j-1];
	}
}
int main(){
	cin>>n>>m;
	cin>>s>>t;
	s_=t+'#'+s;
	kmp();
	for(int i=1;i<=n;i++) if(nxt[i+m]==m) a[i-m+1]=1;
	for(int i=1;i<=n;i++) a[i]+=a[i-1];
	for(int i=1;i<=n;i++) a[i]+=a[i-1];
	manacher();
	for(int i=n;i>=1;i--) dp[i]=dp[i-1];
	for(int i=1;i<=n;i++){
		if(2*dp[i]+1<m) continue;
		len=2*dp[i]+3-m;
		ans+=a[i+dp[i]-m+1]-a[max(i+dp[i]-m+1-(len/2),0)];
		ans-=a[i-dp[i]+len/2-2]-(i-dp[i]-1?a[i-dp[i]-2]:0);
	}
	cout<<ans;
	return 0;
}
2025/7/3 21:37
加载中...