#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
 
int modulo=91; //od tego zalezy ile będzie pozycji w tablicy, proponowałbym liczbe pierwszą w okolicach np. ilosc wyrazow / 2 albo /3
 
struct Node
  {
    char* val;
    Node* next;
  };
 
int hash(const char* slowo);
void add(char* klucz, Node*& lista);
void search(char* klucz, Node* lista);
 
int main()
{
  char* buf=new char[150]; //zakładam ze dłuższego slowa nie będzie :P
  int ile;
  cout<<"Ile elementow?"<<endl;
  cin>>ile;
 
  Node** tablica = new Node*[modulo]; //nasza tablica z hashująca
  for (int i=0;i<modulo;i++)
    tablica[i]=NULL;
 
  for (int i=0;i<ile;i++)
  {
    cin>>buf; //wczytywanie wyrazów do tablicy
    char* str = new char[150];
    strcpy(str,buf);
    add(str, tablica[hash(str)]); //dodawanie kolejnych wyrazów do tablicy
  }
 
  for (int i=0;i<modulo;i++) //wypisanie tablicy
  {
    Node* rob=tablica[i];
    cout<<"Tablica["<<i<<"] =";
    while(rob)
      {
        cout<<" "<<rob->val;
        rob=rob->next;
      }
    cout<<endl;
  }
 
  cout<<"Czego szukac?"<<endl;
  cin>>buf;
  search(buf, tablica[hash(buf)]);
 
  cin.sync();
  cin.get();
  return EXIT_SUCCESS;
}
//////////////////////////////////////////////////////////
int hash(const char* slowo)
{
  int ret=0;
  int n=strlen(slowo); //dlugosć słowa
 
  while(n>=sizeof(int)) //dopóki są kawałki po 4 bajty
  {
   ret^=*(int*)slowo; //xor na 4 bajtach
   n-=sizeof(int); //"skracamy słowo"
   slowo+=sizeof(int); //przesuwamy sie dalej
  }
 
  int rem=0; //to co nam zostało, tzn 1,2 lub 3 bajty
  while(n--)
  {
    rem<<=8; //przesuwamy się o 1 bajt
    rem^=*slowo++; //xor
  }
  ret^=rem;
  return ret%modulo;
}
//////////////////////////////////////////////////////////
void add(char* klucz, Node*& lista)
{
  Node* tmp = new Node;
  tmp->val = klucz;
  tmp->next = lista;
  lista=tmp;
}
/////////////////////////////////////////////////////////////
void search(char* klucz, Node* lista)
{
  int ile = 1;
  if (!lista)
    cout<<"Brak, lista dla danego hasha pusta"<<endl;
  else
    {
      while((lista) && (strcmp(lista->val,klucz)))
      {
        lista=lista->next;
        ile++;
      }
      if (lista && !strcmp(lista->val,klucz))
        cout<<klucz<<" znalezione po "<<ile<<" porownaniach"<<endl;
    }
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGNzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKaW50IG1vZHVsbz05MTsgLy9vZCB0ZWdvIHphbGV6eSBpbGUgYsSZZHppZSBwb3p5Y2ppIHcgdGFibGljeSwgcHJvcG9ub3dhxYJieW0gbGljemJlIHBpZXJ3c3rEhSB3IG9rb2xpY2FjaCBucC4gaWxvc2Mgd3lyYXpvdyAvIDIgYWxibyAvMwogCnN0cnVjdCBOb2RlCiAgewogICAgY2hhciogdmFsOwogICAgTm9kZSogbmV4dDsKICB9OwogCmludCBoYXNoKGNvbnN0IGNoYXIqIHNsb3dvKTsKdm9pZCBhZGQoY2hhcioga2x1Y3osIE5vZGUqJiBsaXN0YSk7CnZvaWQgc2VhcmNoKGNoYXIqIGtsdWN6LCBOb2RlKiBsaXN0YSk7CiAKaW50IG1haW4oKQp7CiAgY2hhciogYnVmPW5ldyBjaGFyWzE1MF07IC8vemFrxYJhZGFtIHplIGTFgnXFvHN6ZWdvIHNsb3dhIG5pZSBixJlkemllIDpQCiAgaW50IGlsZTsKICBjb3V0PDwiSWxlIGVsZW1lbnRvdz8iPDxlbmRsOwogIGNpbj4+aWxlOwogCiAgTm9kZSoqIHRhYmxpY2EgPSBuZXcgTm9kZSpbbW9kdWxvXTsgLy9uYXN6YSB0YWJsaWNhIHogaGFzaHVqxIVjYQogIGZvciAoaW50IGk9MDtpPG1vZHVsbztpKyspCiAgICB0YWJsaWNhW2ldPU5VTEw7CiAKICBmb3IgKGludCBpPTA7aTxpbGU7aSsrKQogIHsKICAgIGNpbj4+YnVmOyAvL3djenl0eXdhbmllIHd5cmF6w7N3IGRvIHRhYmxpY3kKICAgIGNoYXIqIHN0ciA9IG5ldyBjaGFyWzE1MF07CiAgICBzdHJjcHkoc3RyLGJ1Zik7CiAgICBhZGQoc3RyLCB0YWJsaWNhW2hhc2goc3RyKV0pOyAvL2RvZGF3YW5pZSBrb2xlam55Y2ggd3lyYXrDs3cgZG8gdGFibGljeQogIH0KIAogIGZvciAoaW50IGk9MDtpPG1vZHVsbztpKyspIC8vd3lwaXNhbmllIHRhYmxpY3kKICB7CiAgICBOb2RlKiByb2I9dGFibGljYVtpXTsKICAgIGNvdXQ8PCJUYWJsaWNhWyI8PGk8PCJdID0iOwogICAgd2hpbGUocm9iKQogICAgICB7CiAgICAgICAgY291dDw8IiAiPDxyb2ItPnZhbDsKICAgICAgICByb2I9cm9iLT5uZXh0OwogICAgICB9CiAgICBjb3V0PDxlbmRsOwogIH0KIAogIGNvdXQ8PCJDemVnbyBzenVrYWM/Ijw8ZW5kbDsKICBjaW4+PmJ1ZjsKICBzZWFyY2goYnVmLCB0YWJsaWNhW2hhc2goYnVmKV0pOwogCiAgY2luLnN5bmMoKTsKICBjaW4uZ2V0KCk7CiAgcmV0dXJuIEVYSVRfU1VDQ0VTUzsKfQovLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCmludCBoYXNoKGNvbnN0IGNoYXIqIHNsb3dvKQp7CiAgaW50IHJldD0wOwogIGludCBuPXN0cmxlbihzbG93byk7IC8vZGx1Z29zxIcgc8WCb3dhCiAKICB3aGlsZShuPj1zaXplb2YoaW50KSkgLy9kb3DDs2tpIHPEhSBrYXdhxYJraSBwbyA0IGJhanR5CiAgewogICByZXRePSooaW50KilzbG93bzsgLy94b3IgbmEgNCBiYWp0YWNoCiAgIG4tPXNpemVvZihpbnQpOyAvLyJza3JhY2FteSBzxYJvd28iCiAgIHNsb3dvKz1zaXplb2YoaW50KTsgLy9wcnplc3V3YW15IHNpZSBkYWxlagogIH0KIAogIGludCByZW09MDsgLy90byBjbyBuYW0gem9zdGHFgm8sIHR6biAxLDIgbHViIDMgYmFqdHkKICB3aGlsZShuLS0pCiAgewogICAgcmVtPDw9ODsgLy9wcnplc3V3YW15IHNpxJkgbyAxIGJhanQKICAgIHJlbV49KnNsb3dvKys7IC8veG9yCiAgfQogIHJldF49cmVtOwogIHJldHVybiByZXQlbW9kdWxvOwp9Ci8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8Kdm9pZCBhZGQoY2hhcioga2x1Y3osIE5vZGUqJiBsaXN0YSkKewogIE5vZGUqIHRtcCA9IG5ldyBOb2RlOwogIHRtcC0+dmFsID0ga2x1Y3o7CiAgdG1wLT5uZXh0ID0gbGlzdGE7CiAgbGlzdGE9dG1wOwp9Ci8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8Kdm9pZCBzZWFyY2goY2hhcioga2x1Y3osIE5vZGUqIGxpc3RhKQp7CiAgaW50IGlsZSA9IDE7CiAgaWYgKCFsaXN0YSkKICAgIGNvdXQ8PCJCcmFrLCBsaXN0YSBkbGEgZGFuZWdvIGhhc2hhIHB1c3RhIjw8ZW5kbDsKICBlbHNlCiAgICB7CiAgICAgIHdoaWxlKChsaXN0YSkgJiYgKHN0cmNtcChsaXN0YS0+dmFsLGtsdWN6KSkpCiAgICAgIHsKICAgICAgICBsaXN0YT1saXN0YS0+bmV4dDsKICAgICAgICBpbGUrKzsKICAgICAgfQogICAgICBpZiAobGlzdGEgJiYgIXN0cmNtcChsaXN0YS0+dmFsLGtsdWN6KSkKICAgICAgICBjb3V0PDxrbHVjejw8IiB6bmFsZXppb25lIHBvICI8PGlsZTw8IiBwb3Jvd25hbmlhY2giPDxlbmRsOwogICAgfQp9

NApBbGEKT2xhCkVsYQpVbGEKQWxh

4
Ala
Ola
Ela
Ula
Ala