给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数H(Key)将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。例如将字符串AZDEG插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为3×32^2+4×32+6=3206；然后根据表长得到，即是该字符串的散列映射位置。

发生冲突时请用平方探测法解决。

输入格式:
输入第一行首先给出两个正整数N（≤500）和P（≥2N的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个字符串关键字，每个长度不超过8位，其间以空格分隔。

输出格式:
在一行内输出每个字符串关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

输入样例1:

4 11
HELLO ANNK ZOE LOLI

输出样例1:

3 10 4 0

输入样例2:

6 11
LLO ANNA NNK ZOJ INNK AAA

输出样例2:

3 0 10 9 6 1

代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXS 8//最大字符串长度
#define MAXD 3//参与散列映射计算的字符的个数
#define MAXB 5//每个字符占的位数
#define Mask ((1<<(MAXD*MAXB))-1)//掩码32^3-1

typedef char ElementType[MAXS+1];
enum EntryType{Legitimate, Empty};
struct HashEntry{
    ElementType Element;
    enum EntryType Info;
};
struct HashTbl{
    int TableSize;
    struct HashEntry *TheCells;
};
typedef struct HashTbl *HashTable;

HashTable InitializeTable(int TableSize);//散列表初始化
int Hash(char *Key, int P);//字符串Key最后D位移位法散列函数
int Find(char *Key, HashTable H);//返回Key的位置，或是适合插入Key的位置
void InsertAndOutput(char *Key, HashTable H);//插入Key并输出其位置

int main()
{
    int N, P;
    ElementType Key;
    HashTable H;
    scanf("%d%d",&N,&P);
    H = InitializeTable(P);//创建散列表
    scanf("%s",Key);
    InsertAndOutput(Key, H);//输出第一个关键字的位置
    for(int i=1;i<N;i++){
        scanf("%s",Key);
        printf(" ");//后续输出数字前有空格
        InsertAndOutput(Key, H);
    }
    printf("\n");
    return 0;
}

HashTable InitializeTable(int TableSize){
    HashTable H = malloc(sizeof(struct HashTbl));
    H->TableSize = TableSize;
    H->TheCells = malloc(sizeof(struct HashEntry) * H->TableSize);
    while(TableSize)
        H->TheCells[--TableSize].Info = Empty;
    return H;
}

int Hash(char *Key, int P){
    int h = 0;
    while(*Key!='\0')
        h = (h<<MAXB) + (*Key++ -'A');//可理解为h为32进制的数，每位的大小为Key中对应字符按字母表排序的序号
    return ((h&Mask) % P);//h和Mask按位与消除后三位之前的部分，再除以P的散列位置 
}

int Find(char *Key, HashTable H){
    int inc, Cnt=0, Next, Pos;//inc为探测步长，Cnt为冲突次数，Next为最终位置，Pos为散列映射位置
    Next = Pos = Hash(Key, H->TableSize);//先找到散列映射后的位置
    while((H->TheCells[Next].Info!=Empty)&&(strcmp(H->TheCells[Next].Element, Key))){//若该位置已被其他关键字占用
        if(++Cnt%2) inc = ((Cnt+1)*(Cnt+1))>>2;//奇数次冲突时探测步长为((Cnt+1)/2)^2
        else inc = -(Cnt*Cnt)>>2;//偶数次冲突时探测步长为(Cnt/2)^2
        Next = Pos + inc;//平方探测
        if(Next<0) Next += H->TableSize;
        else if(Next >= H->TableSize) Next -= H->TableSize;
    }
    return Next;
}

void InsertAndOutput(char *Key, HashTable H){
    int Pos = Find(Key, H);
    if(H->TheCells[Pos].Info==Empty){//插入
        H->TheCells[Pos].Info = Legitimate;
        strcpy(H->TheCells[Pos].Element, Key);
    }
    printf("%d",Pos);
}