HDU2594 Simpsons’ Hidden Talents 字符串哈希

最近在学习字符串的知识，在字符串上我跟大一的时候是没什么区别的，所以恶补了很多基础的算法，今天补了一下字符串哈希，看的是大一新生的课件学的，以前觉得字符串哈希无非就是跟普通的哈希没什么区别，倒也没觉得有什么特别大的用处，敲一敲才发现其实讲究还是比较多的。哈希冲突是常有的事，换一下mod，换一下进制数才有可能过，另外一种说法是用两个互质的量做hash，如果两个都相等的话那冲突就会少很多，这个倒没有做过多大的尝试，侥幸地过了一下这道题

#pragma warning(disable:4996)

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<string>

#include<algorithm>

#define maxn 50000

#define mod 40157

#define xx 133

using namespace std;

char s[maxn + 50];

char t[maxn + 50];

int h1[maxn + 50];

int h2[maxn + 50];

int xpow[maxn+50];

int main()

{

	xpow[0] = 1;

	for (int i = 1; i <= maxn + 20; i++)

		xpow[i] = xpow[i - 1] * xx%mod;

	while (~scanf("%s%s", s + 1,t + 1))

	{

		h1[0] = h2[0] = 0;

		int n = strlen(s+1), m = strlen(t+1);

		for (int i = 1; i <= n; i++) h1[i] = (h1[i - 1] * xx%mod + s[i])%mod;

		for (int i = 1; i <= m; i++) h2[i] = (h2[i - 1] * xx%mod + t[i])%mod;

		int ans = 0;

		int len = min(n, m);

		for (int i = 1; i <= len; i++){

			int lhs = (h1[i] - h1[0] * xpow[i] % mod + mod) % mod;

			int rhs = (h2[m] - h2[m - i] * xpow[i]% mod + mod) % mod;

			if (lhs == rhs) ans = i;

		}

		if (!ans) puts("0");

		else{

			for (int i = 1; i <= ans; i++){

				printf("%c", s[i]);

			}

			printf(" %d\n", ans);

		}

	}

	return 0;

}

巴特西

HDU2594 Simpsons’ Hidden Talents 字符串哈希

最新文章

热门文章