比赛 CSP2023-J模拟赛 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 切分子串 最终得分 100
用户昵称 嗨嗨嗨 运行时间 0.009 s
代码语言 C++ 内存使用 0.29 MiB
提交时间 2023-10-18 19:44:18
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
string s,t;
int ans,ls,lt;
unsigned long long p[2010],fs[2010],ft[160],P=13331,tmp1,tmp2,flag1,flag2;
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main()
{
    freopen("cutstring.in","r",stdin);
    freopen("cutstring.out","w",stdout);
    cin>>s>>t;
    ls=s.length(),lt=t.length();
    p[0]=1;
    for(int i=0;i<ls;i++)
    {
        fs[i+1]=fs[i]*P+(s[i]-'a'+1);
        p[i+1]=p[i]*P;
    }
    for(int i=0;i<lt;i++) ft[i+1]=ft[i]*P+(t[i]-'a'+1);
    for(int i=1;i<lt;i++) 
    {
		flag1=0;
		flag2=0;
		tmp1=ft[i]-ft[0]*p[i+1];
		tmp2=ft[lt]-ft[i]*p[lt-i];
		for(int j=1;j<=ls-i+1;j++)
		{
			int k=j+i-1;
			if(fs[k]-fs[j-1]*p[k-j+1]==tmp1)
			{
				flag1=1;
				break; 
			}
		}
		for(int j=1;j<=ls-lt+i+1;j++)
		{
			int k=j+lt-i-1;
			if(fs[k]-fs[j-1]*p[k-j+1]==tmp2)
			{
				flag2=1;
				break; 
			}
		}
		if(flag1&&flag2) ans++;
	}
	write(ans);
    return 0;
}