【dtoj begin#4211】「TDog 2021 S Day5 」单词

传送门

题目描述

给你两个由小写字母组成的单词 $A$ 和 $B$，我们称一个单词为幸运单词，当且仅当它是由 $A$ 的某个非空前缀和 $B$ 的某个非空后缀拼接而成的（ $A$ 的前缀在 $B$ 的后缀的前面）。

例如，当单词 $A$ 为 $tree$，单词 $B$ 为 $heap$ 时， $trap$ 就是一个幸运单词，而 $traep,aptr$ 则不是。

请问对于给定的单词 $A$ 和 $B$，共有多少个不同的幸运单词？

输入格式

输入包含两行，第一行为单词 A，第二行为单词 B。

输出格式

输出一个整数，表示幸运单词的总个数。

样例输入

cat
dog

样例输出

9

数据范围与提示

对$20\%$的数据，单词A的长度$lengt{h}_A$和单词B的长度$lengt{h}_B$满足，$1\le lengt{h}_A,lengt{h}_B\le 100$；
对$40\%$的数据，$1\le lengt{h}_A,lengt{h}_B\le 10^3$；
对$100\%$的数据，$1\le lengt{h}_A,lengt{h}_B\le 10^5$ 。

题解

先上结论：答案是$lengt{h}_A\times lengt{h}_B-{\sum }_i{x}_i\times y_i$（其中$x_i，y_i$分别是单词A、单词B中字母i的个数）
理解的方式有很多，我的理解是这样的：（两个单词长度相乘不用说）
单词B的后缀等价于前后反转后的前缀倒过来。
把单词A中的字母表示为$a_1,a_2,...,a_n$，反转后的单词B中的字母表示为$b_1,b_2,...,b_m$。
易知只有长度相同的单词才会出现重复的情况。那么，随便举个例子，长度为5的拼接后单词可能为：
$a_1{b}_4{b}_3{b}_2{b}_1$
$a_1{a}_2{b}_3{b}_2{b}_1$
$a_1{a}_2{a}_3{b}_2{b}_1$
$a_1{a}_2{a}_3{a}_4{b}_1$
其中，若$a_2$和$b_4$相同，就会带来一次重复的计算。
若$a_3$和$b_3$相同，也会带来一次重复的计算。
……
然而我们发现，除了A的首字母和B的尾字母，在拼接后单词不同的长度下，所有的相同字母都可以这样组成配对，带来重复的计算。所以就可以推出重复计算的总个数。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e5+5;
ll ans,al,bl,bka[30],bkb[30];
char A[M],B[M];
int main(){
	scanf("%s%s",&A,&B);
	al=strlen(A);
	bl=strlen(B);
	for(int i=1;i<al;i++) bka[(int)(A[i]-'a')]++;
	for(int i=0;i<bl-1;i++) bkb[(int)(B[i]-'a')]++;
	ans+=al*bl;
	for(int i=0;i<=25;i++) ans-=bka[i]*bkb[i];
	printf("%lldn",ans);
	return 0;
}

Thanks!

最后

以上就是曾经枫叶为你收集整理的【dtoj begin#4211】「TDog 2021 S Day5 」单词的全部内容，希望文章能够帮你解决【dtoj begin#4211】「TDog 2021 S Day5 」单词所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。