C++：[NWRRC2015] Concatenation（洛谷）P7050

题目描述

Famous programmer Gennady likes to create new words. One way to do it is to concatenate existing words. That means writing one word after another. For example, if he has words cat and dog, he would get a word catdog, that could mean something like the name of a creature with two heads: one cat head and one dog head.

Gennady is a bit bored of this way of creating new words, so he has invented another method. He takes a non-empty prefix of the first word, a non-empty suffix of the second word, and concatenates them. For example, if he has words tree and heap, he can get such words as treap, tap, or theap. Who knows what they could mean?

Gennady chooses two words and wants to know how many different words he can create using his new method. Of course, being a famous programmer, he has already calculated the answer. Can you do the same?

输入格式

Two lines of the input file contain words chosen by Gennady. They have lengths between 11 and 100000100000 characters and consist of lowercase English letters only.

输出格式

Output one integer -- the number of different words Gennady can create out of words given in the input file.

题意翻译

题目描述

著名的程序员 Gennady 喜欢创造新单词。其中一种方法是连接现有单词。

举个例子：如果 Gennady 有 cat 和 dog 两个词，那么他会得到一个新词： catdog，这可能意味着带有两个头的生物的名字：一个猫头和一个狗头。

Gennady 觉得这种创建新单词的方式有点无聊，因此他发明了另一种方法：使用第一个单词的非空前缀，第二个单词的非空后缀，并将它们连接起来。例如，如果他有单词 tree 和 heap ，则可以得到诸如 treap，tap 或 theap 之类的单词。

Gennady 选择了两个单词，并想知道他可以使用新方法创建多少个不同的单词。当然，作为著名的程序员，他已经计算出了答案。他突然想考考你，那么你能编写一个程序把答案计算出来吗？

输入格式

两行，每行有一个 Gennady 选择的单词 si​​ （1≤∣si​∣≤100000），si​ 仅由小写英文字母组成）。

输出格式

输出一个整数，这个整数表示 Gennady 可以从这两个给定的单词中创建不同单词的数量。

输入输出样例

输入 #1

cat
dog

输出 #1

9

输入 #2

tree
heap

输出 #2

14

说明/提示

Time limit: 2 s, Memory limit: 256 MB.

解析：

题目大意：

求两个单词能组成多少个新单词。

举例：

首先我们先拿两个单词来举例一下：

第一种是没有重复的情况：

dogdog 与 catcat。

它们能够组成的单词如下：

dcat , dat , dt , docat , doat , dot , dogcat , dogat , dogt dcat , dat , dt , docat , doat , dot , dogcat , dogat , dogt 

第二种是有重复的情况：

treetree 与 heapheap。

它们能够组成的单词如下：

theap , teap , tap , tp , trheap , treap , trap , trp , trehaep , treeap , treap , trep , treeheap , treeeap , treeap , treep theap , teap , tap , tp , trheap , treap , trap , trp , trehaep , treeap , treap , trep , treeheap , treeeap , treeap , treep 

我们能发现在这些新单词中有重复的，我们就将重复的删除掉。

剩下的单词： theap , teap , tap , tp , trheap , trap , trp , trehaep , treap , trep , treeheap , treeeap , treeap , treep theap , teap , tap , tp , trheap , trap , trp , trehaep , treap , trep , treeheap , treeeap , treeap , treep 

思路：

构成方法：用第一个单词的非空前缀，用第二个单词的非空后缀。

那么我们可以用 ans 记录答案，再初始化设为两个单词长度之积，就是能创造的所有单词。

而前面我们已将两种情况都举例了一遍，就可以先减去所有重复单词，且重复单词就是两个单词相同的字母数量乘积，最后输出。

话不多说，上code：

#include <bits/stdc++.h>
using namespace std;
const int N=2e1+6;
string s1,s2;
long long a[N],b[N];
long long ans,x,y;
int main(){
	cin>>s1>>s2;
	x=s1.size(),y=s2.size();
	for(int i=1;i<x;i++)
		a[s1[i]-'a']++;
	for(int i=0;i<y-1;i++)
		b[s2[i]-'a']++;
	for(int i=0;i<26;i++)	
		ans+=a[i]*b[i];
	printf("%lld",x*y-ans);
	return 0;
}

记得点个赞哟！