Codeforces I. Palindrome Pairs （Hash）

I. Palindrome Pairs

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

After learning a lot about space exploration, a little girl named Ana wants to change the subject.

Ana is a girl who loves palindromes (string that can be read the same backwards as forward). She has learned how to check for a given string whether it's a palindrome or not, but soon she grew tired of this problem, so she came up with a more interesting one and she needs your help to solve it:

You are given an array of strings which consist of only small letters of the alphabet. Your task is to find how many palindrome pairs are there in the array. A palindrome pair is a pair of strings such that the following condition holds: at least one permutation of the concatenation of the two strings is a palindrome. In other words, if you have two strings, let's say "aab" and "abcac", and you concatenate them into "aababcac", we have to check if there exists a permutation of this new string such that it is a palindrome (in this case there exists the permutation "aabccbaa").

Two pairs are considered different if the strings are located on different indices. The pair of strings with indices (i,j)(i,j) is considered the same as the pair (j,i)(j,i).

Input

The first line contains a positive integer NN (1≤N≤1000001≤N≤100000), representing the length of the input array.

Eacg of the next NN lines contains a string (consisting of lowercase English letters from 'a' to 'z') — an element of the input array.

The total number of characters in the input array will be less than 10000001000000.

Output

Output one number, representing how many palindrome pairs there are in the array.

Examples

input

Copy

3
aa
bb
cd

output

Copy

1

input

Copy

6
aab
abcac
dffe
ed
aa
aade

output

Copy

6

Note

The first example:

1. aa ++ bb →→ abba.

The second example:

1. aab ++ abcac == aababcac →→ aabccbaa
2. aab ++ aa == aabaa
3. abcac ++ aa == abcacaa →→ aacbcaa
4. dffe ++ ed == dffeed →→ fdeedf
5. dffe ++ aade == dffeaade →→ adfaafde
6. ed ++ aade == edaade →→ aeddea

题目链接：http://codeforces.com/problemset/problem/1045/I

题目大意：给出若干个字符串，任意两个字符串可任意拼接组合，就是把两个字符串的字母都取出来，然后再重新组成新字符串，求有多少对字符串拼接后能构成回文串。

思路：根据回文串的性质，如果一个串是回文串，那么最多只有一个字母出现奇数次，其余的都为偶数， 或者都为偶数次。那么就统计一下每一个串中每一种字母的个数，转化成01串的形式，将这个01串作为这个串的hash值。

在查找的时候，只需要找出了自己和本身相同的hash加上与自身01串只有一位hash值不同的串，最后除以2即可。

还要注意最后答案要用long long储存，否则WA。。。

/*
@Author: Top_Spirit
@Language: C++
*/
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std ;
typedef long long ll ;
const int Maxn = 1e5 +10 ;

unordered_map < string, int > uma ;
string s[Maxn], str ;
int cnt[30] ;

int main (){
    int n ;
    cin >> n ;
    for (int i = 1; i <= n; i++){
        cin >> str ;

        fill(cnt, cnt + 30, 0) ;
        for (auto i : str){
            cnt[i - 'a']++ ;
        }
        string tmp = "" ;
        for (int j = 0; j < 26; j++){
            tmp += (cnt[j] % 2 ) + '0' ; // 转化为01川
        }
        s[i] = tmp ;
        uma[tmp]++ ;
    }
    ll ans = 0 ;
    for (int i = 1; i <= n; i++){
        string tmp = s[i] ;
        ans += uma[tmp] - 1 // 除本身之外hash值相同的个数
        for (int j = 0; j < 26; j++){
            tmp = s[i] ;
            if (tmp[j] == '0') tmp[j] = '1' ;
            else tmp[j] = '0' ;
            ans += uma[tmp] ;  // 只有一位hash值不同的个数
        }
    }
    cout << (ans >> 1) << endl ;
    return 0 ;
}

这里说一下map和unordered_map的差别

map: #include < map >
unordered_map: #include < unordered_map >

map： map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。
unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。

map：

优点：

有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作。
红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高。
缺点： 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间。

适用处：对于那些有顺序要求的问题，用map会更高效一些。

unordered_map：

优点： 因为内部实现了哈希表，因此其查找速度非常的快
缺点： 哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map
总结：

内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。
但是unordered_map执行效率要比map高很多
对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的。

晚来天欲雪

能饮一杯元

最后

以上就是奋斗鸡为你收集整理的Codeforces I. Palindrome Pairs （Hash）的全部内容，希望文章能够帮你解决Codeforces I. Palindrome Pairs （Hash）所遇到的程序开发问题。

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