2023王道C语言训练营（哈希查找，串--KMP）

#define MaxKey 1000
#include 

//不需要记，考研绝对不会让你写
int hash(const char* key)
{
	int h = 0, g;
	while (*key)
	{
		h = (h << 4) + *key++;
		g = h & 0xf0000000;
		if (g)
		{
			h ^= g >> 24;
		}
		h &= ~g;
	}
	//算出下标要取余
	return h % MaxKey;
};

int main()
{
	//字符指针数组
	const char* pStr[5] = { "xiongda","lele","hanmeimei","wangdao","fengren" };
	int i;
	const char* pHash_table[MaxKey] = { NULL };//哈希表，散列表
	for (i = 0; i < 5; i++)
	{							//字符串   下标
		printf("%s is key=%dn", pStr[i], hash(pStr[i]));
		pHash_table[hash(pStr[i])] = pStr[i];
	}
	return 0;
}

#define  _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 

typedef char* SString;

//S  abcabaaabaabcac
//T  abaabcac
//为什么从1位置开始比较，因为0号位置存储了字符串的长度
int Index(SString S, SString T)
{

	int i = 1, j = 1;
	while (i <= S[0] && j <= T[0])
	{
		if (S[i] == T[j])
		{
			++i, ++j;//继续比较后续字符
		}
		else {
			i = i - j + 2; j = 1;//指针后退重新开始匹配
		}
	}
	if (j > T[0]) return i - T[0];//匹配成功
	else return 0;
};
//i游标，遍历T
void get_next(char T[], int next[])
{
	int i = 1;
	next[1] = 0;//恒为0
	int j = 0;
	//abaabcac
	while(i < T[0])//T[0]中记录了字符串的长度
	{
		if (j == 0 || T[i] == T[j])//j==0,说明再次回到了开头
		{
			++i; ++j;
			next[i] = j;//记录出现重复的位置
		}
		else {
			j = next[j];//不相同，找个位置重新比较
		}
	}
}
//S  abcabaaabaabcac
//T  abaabcac
int KMP(char S[], char T[], int next[], int pos)
{
	int i = pos;//开始查找的起始位置
	int j = 1;
	while (i <= S[0] && j <= T[0])
	{
		if (j == 0 || S[i] == T[j]) {
			//相等各自加加
			++i;
			++j;
		}
		else//不等，就回退next[j]的位置
			j = next[j];
	}
	if (j > T[0])//说明比对成功
		return i - T[0];
	else
	{
		return 0;
	}

}
int main()
{
	//字符串进行初始化
	char S[256];
	char T[10];
	int next[10];
	int pos;
	S[0] = strlen("abcabaaabaabcac");//strlen里有多少个字符
	strcpy(S + 1, "abcabaaabaabcac");
	T[0] = strlen("abaabcac");
	strcpy(T + 1, "abaabcac");
	//暴力匹配
	pos = Index(S, T);
	if (pos)
	{
		printf("匹配成功，位置为%dn", pos);
	}
	else {
		printf("未匹配n");
	}
	get_next(T, next);//算出next数组
	pos = KMP(S, T, next, 1);
	if (pos)
	{
		printf("匹配成功，位置为%dn", pos);
	}
	else {
		printf("未匹配n");
	}
	system("pause");


}