#include<bits/stdc++.h> using namespace std; #define int long long #define lson (pos<<1) #define rson (pos<<1|1) #define fr first #define sc second #define pii pair<int,int> #define mk make_pair #define pb push_back inline int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}x=c-'0';c=getchar();while(c<='9'&&c>='0'){x*=10;x+=c-'0';c=getchar();}return x*f;} const int MAXN=200010,MAXM=1000000,base=131,Mod=1011451423; int n,m,k,hs,p[MAXN],cnt,jc[MAXN]; char a[MAXN],b[MAXN],q[MAXN]; int Hsh(int x,char y){ // cout<<"+"<<y<<endl; return (x*base%Mod+y)%Mod;} int cut(int l,int r){ return (p[r]-p[l-1]*jc[r-l+1]%Mod+Mod)%Mod; } int check(int x){ for(int i=1;i<=x;i++)p[i]=Hsh(p[i-1],a[i]); for(int i=1;i<=m;i++)p[i+x]=Hsh(p[i+x-1],b[i]); for(int i=x+1;i<=n;i++)p[i+m]=Hsh(p[i+m-1],a[i]); int res=0; for(int i=1;i+k-1<=n+m;i++){ res+=cut(i,i+k-1)==hs; } return res; } void slv1(){ int ans0=0,ans1=0; for(int i=0;i<=n;i++){ int tmp=check(i); if(ans0==tmp)ans1++; if(ans0<tmp){ ans0=tmp; ans1=1; } } printf("%lld %lld",ans0,ans1); } int check2(int x){ // cout<<x<<":"; int res=0; if(m<k){cnt=0; for(int i=max(x-k+2,1ll);i<=x;i++)cnt++,p[cnt]=Hsh(p[cnt-1],a[i]); for(int i=1;i<=m;i++)cnt++,p[cnt]=Hsh(p[cnt-1],b[i]); for(int i=x+1;i<=min(k+x-1,n);i++)cnt++,p[cnt]=Hsh(p[cnt-1],a[i]); for(int i=1;i+k-1<=cnt;i++){ res+=cut(i,i+k-1)==hs; } // cout<<res<<endl; return res; } cnt=0; for(int i=max(x-k+2,1ll);i<=x;i++)cnt++,p[cnt]=Hsh(p[cnt-1],a[i]); for(int i=1;i<=min(k-1,m);i++)cnt++,p[cnt]=Hsh(p[cnt-1],b[i]); // cout<<hs<<" "; for(int i=1;i+k-1<=cnt;i++){ // cout<<cut(i,i+k-1)<<" "; res+=cut(i,i+k-1)==hs; } // cout<<endl; cnt=0; for(int i=max(m-k+2,1ll);i<=m;i++)cnt++,p[cnt]=Hsh(p[cnt-1],b[i]); for(int i=x+1;i<=min(k+x-1,n);i++)cnt++,p[cnt]=Hsh(p[cnt-1],a[i]); for(int i=1;i+k-1<=cnt;i++){ res+=cut(i,i+k-1)==hs; } // cout<<res<<endl; return res; } int sm[MAXN]; void slv2(){ int ans=0,ans0=0,ans1=0; cnt=0; for(int i=1;i<=m;i++)cnt++,p[cnt]=Hsh(p[cnt-1],b[i]); for(int i=1;i+k-1<=cnt;i++){ ans+=cut(i,i+k-1)==hs; } cnt=0; for(int i=1;i<=n;i++)cnt++,p[cnt]=Hsh(p[cnt-1],a[i]); for(int i=1;i+k-1<=cnt;i++){ sm[i]=sm[i-1]+(cut(i,i+k-1)==hs); } for(int i=max(1ll,cnt-k+2);i<=n;i++)sm[i]=sm[i-1]; for(int i=0;i<=n;i++){ int tmp=check2(i)+(i>=k?sm[i-k+1]:0)+sm[n]-sm[i]+ans; if(ans0==tmp)ans1++; if(ans0<tmp){ ans0=tmp; ans1=1; } } printf("%lld %lld",ans0,ans1); } void slv(){ scanf("%s",a+1);scanf("%s",b+1);scanf("%s",q+1); n=strlen(a+1);m=strlen(b+1);k=strlen(q+1); jc[0]=1; for(int i=1;i<=n+m;i++)jc[i]=jc[i-1]*base%Mod; hs=0; for(int i=1;i<=k;i++)hs=Hsh(hs,q[i]); if(n<=2000&&m<=2000&&k<=2000)slv1(); else slv2(); } signed main(){ slv(); return 0; }