题解 UVA156 【反片语 Ananagrams】

· · 题解

看到这道题的人，多半是紫书的读者吧。
方法很多，这里介绍两种。

解法一：标准化(by 刘汝佳)

输入字符串后，把字符全部转成小写，然后排序，这样符合条件的字符串(比如zyx和XYZ)就会得到同样的串了。

string repr(const string& s){
    string ans = s;
    for(int i = 0;i < ans.length();i++)
        ans[i] = tolower(ans[i]);
    sort(ans.begin(),ans.end());
    return ans;
}

用一个map来保存处理后的字符串出现的次数，当然也要用一个vector来放输入的字符串。

#include<iostream>
#include<map>
#include<cctype>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
map<string,int> cnt;
vector<string> words;
string repr(const string& s){
    string ans = s;
    for(int i = 0;i < ans.length();i++)
        ans[i] = tolower(ans[i]);
    sort(ans.begin(),ans.end());
    return ans;
}
int main(){
    int n = 0;
    string s;
    while(cin >> s){
        if(s[0] == '#')break;
        words.push_back(s);
        string r = repr(s);
        if(!cnt.count(r))cnt[r] = 0;
        cnt[r] ++;
    }
}

再开一个vector存放答案，如果一个串处理后只出现了一次，那就放入这个vector。
最后给它排序输出即可。 

vector<string> ans;
for(int i = 0;i < words.size();i++)
    if(cnt[repr(words[i])] == 1)ans.push_back(words[i]);
sort(ans.begin(),ans.end());
for(int i = 0;i < ans.size();i++)
    cout << ans[i] << endl;

全部代码：

#include<iostream>
#include<map>
#include<cctype>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
map<string,int> cnt;
vector<string> words;
string repr(const string& s){
    string ans = s;
    for(int i = 0;i < ans.length();i++)
        ans[i] = tolower(ans[i]);
    sort(ans.begin(),ans.end());
    return ans;
}
int main(){
    int n = 0;
    string s;
    while(cin >> s){
        if(s[0] == '#')break;
        words.push_back(s);
        string r = repr(s);
        if(!cnt.count(r))cnt[r] = 0;
        cnt[r] ++;
    }
    vector<string> ans;
    for(int i = 0;i < words.size();i++)
        if(cnt[repr(words[i])] == 1)ans.push_back(words[i]);
    sort(ans.begin(),ans.end());
    for(int i = 0;i < ans.size();i++)
        cout << ans[i] << endl;
    return 0;
}

这份代码的巧妙之处就在于将字符串排序这一操作，不得不佩服刘汝佳老师的智慧。

解法2：哈希(by zycany)

如果你不知道什么是哈希，那么下面的介绍说不定可以帮到你。

例：输入两个个字符串a,b，求b在a中出现了几次。(1\le |b|\le|a|\le10^6)（kkcoding第175题：字符串匹配）
如果暴力枚举判相等，O(|a|\times|b|)肯定超时。
我们可以采用哈希算法，即将字符串通过某种特定的公式转换成一个整数，然后通过整数判相等来求解。
定义一个 \mathrm{BASE} 表示基准值（通常采用超过100的质数，如311），那么字符串S的哈希值即为：

\sum\limits_{i=1}^{|S|}S[i]\times \mathrm{BASE}^i

这样就可以高效的求出答案了。
大家可以自行尝试写出代码，提交在kk上。
也许有人会问：万一哈希值冲突了怎么办？
要知道，这种按进制位生成的哈希值，是基本不可能冲突的。就算出题老师想故意造数据来卡你的哈希，他也非常困难，因为他连你取的BASE都不知道是几。所以冲突问题不必担心。

下面言归正传，如何运用哈希来解决本题？
很简单了。把a~z映射成1至\mathrm{BASE}^{25}存入数组H，然后也不用按进制了，直接求

\sum\limits_{i=1}^{|S|}H[tolower(S[i])-‘a’]

即可。 

ull Hash(const string& str)
{
    string s = str;
    ull ans = 0;
    int len = str.length();
    for(int i = 0;i < len;++ i)
    {
        s[i]=tolower(s[i])-'a';
        ans += H[s[i]];
    }
    return ans;
}

又有一个问题。如果ull溢出了怎么办？
其实溢出就溢出呗，溢出后从0开始，没什么关系。
那么我们用一个map来储存一个哈希值对应的字符串，以及这个哈希值已经出现了几次。记录一下即可。 

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define BASE 311
#define ull unsigned long long
#define p pair<string,int>
map <ull,p> m;
vector <string> ans;
ull H[30]={1};
ull Hash(const string& str)
{
    string s = str;
    ull ans = 0;
    int len = str.length();
    for(int i = 0;i < len;++ i)
    {
        s[i]=tolower(s[i])-'a';
        ans += H[s[i]];
    }
    return ans;
}
int main()
{
    string str;
    for(int i = 1;i < 26;++i)
        H[i] = BASE*H[i-1];
    while(cin >> str && str != "#")
    {
        ull x = Hash(str);
        if(!m[x].second) 
            m[x].first = str;
        ++m[x].second;
    }
    return 0;
}

别忘了把H[0]设成1，否则整个进制位都是0，哈希法失效。
然后遍历整个map，如果某个哈希值只出现了一次，那么就把它对应的字符串放入一个vector，最后对vector进行排序，输出。 

map <ull,p> ::iterator it;
for(it=m.begin();it != m.end();++it)
    if(it->second.second == 1)
        ans.push_back(it->second.first);
sort(ans.begin(),ans.end());
for(int i = 0;i < ans.size();++i)
    cout << ans[i] << endl;

全部代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define BASE 311
#define ull unsigned long long
#define p pair<string,int>
map <ull,p> m;
vector <string> ans;
ull H[30]={1};
ull Hash(const string& str)
{
    string s = str;
    ull ans = 0;
    int len = str.length();
    for(int i = 0;i < len;++ i)
    {
        s[i]=tolower(s[i])-'a';
        ans += H[s[i]];
    }
    return ans;
}
int main()
{
    string str;
    for(int i = 1;i < 26;++i)
        H[i] = BASE*H[i-1];
    while(cin >> str && str != "#")
    {
        ull x = Hash(str);
        if(!m[x].second) 
            m[x].first = str;
        ++m[x].second;
    }
    map <ull,p> ::iterator it;
    for(it=m.begin();it != m.end();++it)
        if(it->second.second == 1)
            ans.push_back(it->second.first);
    sort(ans.begin(),ans.end());
    for(int i = 0;i < ans.size();++i)
        cout << ans[i] << endl;
    return 0;
}

比刘汝佳老师的代码长了一些，但还是相当高效的。很多字符串问题都可以通过哈希算法来加速。

\mathrm{The\ End.}