C++(g++ 7.5.0) 解法, 执行用时: 12ms, 内存消耗: 3872K, 提交时间: 2022-11-29 14:07:42

/*
aaaabaa
aaaaa
*/


/*
对题目的理解：
KMP Extension
*/
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
ll z[N];
ll p[N];
char a[N],b[N];
void get_z(char *b,ll blen){
	z[1]=blen;
	for(ll i=2,left,right=0;i<=blen;i++){
		if(i<=right) z[i]=min(z[i-left+1],right-i+1);
		while(b[i+z[i]]==b[1+z[i]]){
			z[i]++;
		}
		if(i+z[i]-1>right){
			left=i;
			right=i+z[i]-1;
		}
	}
}

void get_p(char*b, ll blen,char* a,ll alen){
	for(ll i=1,left,right=0;i<=alen;i++){
		if(i<=right)	p[i]=min(z[i-left+1],right-i+1);
		while(i+p[i]<=alen&&1+p[i]<=alen&&b[1+p[i]]==a[i+p[i]]){
			p[i]++;
		}
		if(i+p[i]-1>right){
			left=i;
			right=i+p[i]-1;
		}
	}
}

int main(){
	cin>>(a+1)>>(b+1);
	ll alen=strlen(a+1);
	ll blen=strlen(b+1);
	get_z(b,blen);
	get_p(b,blen,a,alen);
	ll ans=0;
	for(int i=1;i<=alen;i++){
		ans+=min(p[i],blen-1);
		if(a[i+p[i]]<b[1+p[i]]){
			ans+=alen-(i+p[i])+1;
		}
	}
	cout<<ans<<endl;
    system("pause");
	return 0;
}

C++(clang++11) 解法, 执行用时: 8ms, 内存消耗: 2172K, 提交时间: 2020-10-28 15:48:27

#include<bits/stdc++.h>
using namespace std;
const int M=200009;
int n,m;
long long ans;
char c[M],b[M];
int nex[M],ext[M];
int main(){
	scanf("%s%s",c+1,b+1);
	n=strlen(c+1);
	m=strlen(b+1);
	nex[1]=m;
	for(int i=2,p=1,a=1;i<=m;++i){
		if(i>=p||i+nex[i-a+1]>=p){
			if(i>=p)p=i;
			while(p<=m&&b[p]==b[p-i+1])p++;
			nex[i]=p-i;
			a=i;
		}
		else nex[i]=nex[i-a+1];
	}
	for(int i=1,p=1,a=1;i<=n;++i){
		if(i>=p||i+nex[i-a+1]>=p){
			if(i>=p)p=i;
			while(p<=n&&p-i+1<=m&&c[p]==b[p-i+1])p++;
			ext[i]=p-i;
			a=i;
		}
		else ext[i]=nex[i-a+1];
	}
	for(int i=1;i<=n;++i){
		if(c[i+ext[i]]<b[ext[i]+1]&&ext[i]<m)ans+=1ll*n-i+1;
		else ans+=1ll*min(ext[i],m-1);
	}
	printf("%lld",ans);
	return 0;
}