给定两个字符串ss和tt，小明想知道有多少对ss的非空前缀连接起来是tt的前缀。 具体地说，设s_is i ​ 是字符串ss长度为ii的前缀，t_jt j ​ 是字符串tt长度为jj的前缀。 对于一对前缀(s_i,s_j)(s i ​ ,s j ​ )（允许i=ji=j）而言，如果s_i+s_j=t_{i+j}s i ​ +s j ​ =t i+j ​ （++表示字符串拼接），那么我们认为这两个ss的前缀拼接后等于tt的一个前缀。 其中1\le |s|,|t|\le 10^51≤∣s∣,∣t∣≤10 5 ，且仅包含小写字母。

#include <bits/stdc++.h>
using namespace std;
int ans;
typedef unsigned long long ikun;
string s,t;
ikun jntms[100005],jntmt[100005],power[100005];
int main()
{
    cin>>s>>t;
    power[0]=1;
    for (int i=1;i<=100000;i++)
    {
    	power[i]=power[i-1]*131;
    }
    for (int i=1;i<=s.size();i++)
    {
    	jntms[i]=jntms[i-1]*131+(s[i-1]-'A'+1);
    }
    for (int i=1;i<=t.size();i++)
    {
    	jntmt[i]=jntmt[i-1]*131+(t[i-1]-'A'+1);
    }
    for (int i=1;i<=s.size();i++)
    {
    	int leftt=1,rightt=s.size(),x=0;
    	while (leftt<=rightt)
    	{
    		int mid=(leftt+rightt)/2;
    		if (i+mid<=t.size()&&jntms[i]+jntms[mid]*power[i]==jntmt[i+mid])
    		{
    			x=max(mid,x);
    			leftt=mid+1;
    		}
    		else
    		{
    			rightt=mid-1;
    		}
    	}
    	ans+=x;
    }
    cout<<ans;
    return 0;
}