Ars Magna
Tingkat Kesulitan: Hard (90 Poin)
Kembali ke /problemDeskripsi
Ars Magna adalah bahasa Latin yang berarti “the great art”. Tapi, Ars Magna juga merupakan anagram dari “anagrams”. Sebuah string disebut anagram string yang lain jika string tersebut dapat membentuk string yang lain dengan cara menyusun ulang karakter-karakternya. Sebagai contoh, berikut adalah beberapa anagram yang terkenal:
Tom Marvolo Riddle -> I am Lord Voldemort
The Morse Code -> Here comes dots
Eleven plus two -> Twelve plus one
Slot machines -> Cash lost in me
Ismail mempunyai dua daftar string, $S$ dan $T$. Dia menyadari bahwa beberapa string di $S$ bisa dijadikan anagram pada string di $T$. Bantulah Ismail untuk mencari banyaknya pasangan string $(S_i, T_j)$ yang merupakan anagram!
Sebagai contoh, misalkan list yang Ismail punya adalah sebagai berikut:
S T
acep fb
sandra cape
ismail pace
zaky liamsi
mirza
acep
bisa menjadi anagram untuk cape
dan pace
, dan ismail
bisa menjadi anagram untuk liamsi
. Sementara sandra
, mirza
, zaky
, dan fb
tidak mempunyai pasangan anagram. Jadi, ada 3 pasangan.
Format Masukan
Baris pertama berisi dua buah bilangan bulat, $N$ dan $M$, yang merupakan banyaknya string pada $S$ dan $T$.
$N$ baris berikutnya masing-masing berisi sebuah string pada list $S$, dan $M$ baris berikutnya masing-masing berisi sebuah string pada list $T$.
Batasan
Untuk 40% kasus:
- $1 \le N, M \le 1000$.
- Panjang tiap string $\le 10$.
Untuk 100% kasus:
- $1 \le N, M \le 100000$.
Untuk semua kasus:
- Panjang tiap string paling tidak 1.
- Tiap string pada masukan hanya berisi huruf
a-z
dan tidak mengandung spasi. - Total panjang seluruh string tidak melebihi 1000000 ($10^6$) karakter.
- Secara formal: $\sum_{i=1}^N length(S_i) + \sum_{i=1}^M length(T_i) \le 1000000$.
Format Keluaran
Keluarkan sebuah bilangan bulat yang menyatakan banyaknya pasangan anagram pada list $S$ dan $T$.
Contoh Masukan 0
5 4
acep
sandra
ismail
zaky
mirza
fb
cape
pace
liamsi
Contoh Keluaran 0
3
Contoh Masukan 1
4 4
a
a
a
b
a
a
b
b
Contoh Keluaran 1
8
Penjelasan 1
String pada tiap list bisa saja mempunyai duplikat, tapi tiap string harus dianggap sebagai string berbeda.