萌新的真ikun代码求调（hash字符串）

给定两个字符串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 ，且仅包含小写字母。

CPP

#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;
}

萌新的真ikun代码求调（hash字符串）

讨论操作

回复

相关推荐

萌新的真ikun代码求调（hash字符串）