P7050题解

· · 题解

这题我们先观察样例。

显然，S_1 和 S_2 可以组成的字符串数量是 S_1 的长度 \times S_2 的长度。

可是如果按照上面的方法计算，样例二因该输出 16，可为什么输出的是 14 呢？

我们来看看它们所构成的字符串。

tp trp trep treep

tap trap treap treeap

teap treap treeap treeeap

theap trheap treheap treeheap

我们可以发现第二行和第三行有两个词重复了，如果减去这两个词的话答案就正确了。

所以，答案 =S_1 的长度 \times S_2 的长度 - 重复的单词数。

两个长度好求，但重复的数量怎么求呢？

首先，我们可以想到用 map 容器。

于是，我们可以写出下面的代码。

#include<iostream>
#include<map>
using namespace std;
map<string,bool> t;
int main(){
    string a,b;
    cin>>a>>b;
    for(int i=1;i<=a.size();i++){
        for(int j=0;j<b.size();j++) {
            string c=a.substr(0,i)+b.substr(j);
            t[c]=1;
        }
    }
    cout<<t.size();
}

MLE 了。

那我们想想还有什么方法可以得到重复的数量。

再次观察样例二后发现，重复的数量就是两个单词的相同字母数量之积。

为什么每出现一个相同的字母，就会有重复的单词出现呢？

就拿 tree 和 heap 证明一下：

可见，两个词中重复的字母是可以构成的重复词为:

treap 和 treeap

我们在设 a 为字符串 1 的非空前缀 +x，b 为 x+ 字符串 2 的非空后缀，重复的字母为 x。

可得 (a-x)+b=a+(b-x)。

其中 - 的意思就是去掉这个字母。

所以，我们只需要开两个数组分别记录两个字符串中每个字母的出现次数，然后计算出有多少重复的字母就好了。

ACCODE

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