Hamming-távolság

Az információelméletben két azonos hosszúságú kód (sztring) Hamming-távolságán az eltérő jelek (karakterek) számát értjük. Pl. a "harap" és "harag" sztringek Hamming-távolsága 1, mert csupán egyetlen (az utolsó) karakterben térnek el egymástól. Az "almafa" és a "blabla" Hamming távolsága 4, hiszen a második és a hatodik karakter kivételével a többi négy pozícióban eltérnek egymástól. Egy szótár (szavak halmaza) minimális Hamming-távolságán a szótár bármely két szava közötti Hamming-távolságok minimumát értjük. Pl. tekintsük az alábbi négy szót: a="0001111", b="0010110", c="0100101", d="1001011". Az a, b, c és d szavak alkotta szótár minimális Hamming-távolsága 2, mivel H(a,b)=3, H(a,c)=3, H(a,d)=2, H(b,c)=4, H(b,d)=5 és H(c,d)=5, és ezek minimuma 2. Készítsen programot, amely meghatározza egy szótár minimális Hamming-távolságát!

A bemenet specifikációja

A bemenet első sorában egy egynél nagyobb pozitív egész szám (egy szótár mérete) helyezkedik el, majd soronként a szótár szavai jelennek meg. Feltételezzük, hogy a szótár szavai azonos hosszúságúak, és csak az angol abécé kis- és nagybetűit (amelyek között különbséget teszünk!), illetve a számjegyeket tartalmazzák!

A kimenet specifikációja

A kimenet egyetlen sorból áll, amelyben egyetlen szám, a kiszámított minimális Hamming-távolság jelenik meg.

Példa bemenet

1. 4
2. 0001111
3. 0010110
4. 0100101
5. 1001011

Példa kimenet

1. 2