주간 15 문자열 해시 (HDU - 1880)

제목 개술
ZJM 은 호 그 와트 의 기 말고 사 를 준비 하기 위해 저주 사전 을 외우 기로 결심 했다. 주문 번역 문제 라 이브 러 리 형식: [저주] 대응 기능 이 문제 라 이브 러 리 를 외 운 후에 ZJM 은 문 제 를 풀 기 시작 했다. 현재 N 문제 가 있 는데 문제 마다 문자열 을 주 었 다. [저주] 일 수도 있 고 대응 기능 ZJM 이 이 문 제 를 식별 해 야 하 는 것 이 [저주] 인지 대응 기능 일 수도 있다.변환 결 과 를 쓰 고 저주 사전 에서 찾 지 못 하면 "what?" 를 출력 합 니 다.
입력 샘플
먼저 저주 사전 에 100000 개가 넘 지 않 는 주문 을 열거 합 니 다. 각 형식 은:
[저주] 대응 기능 [저주] 대응 기능 [저주] 대응 기능
그 중에서 '저주' 와 '대응 기능' 은 각각 길이 가 20 과 80 을 초과 하지 않 는 문자열 로 문자열 에 문자 '[' 와 ']' 가 포함 되 지 않 고 ']' 와 뒤의 문자열 사이 에 빈 칸 만 있 음 을 보증 합 니 다.저주 사전 의 마지막 줄 은 '@ END @' 으로 끝 납 니 다. 이 줄 은 사전 의 단어 에 속 하지 않 습 니 다.사전 뒤의 한 줄 은 정수 N (< = 1000) 을 포함 하고 그 다음은 N 개의 테스트 용례 이다.각 테스트 용례 가 한 줄 을 차지 하거나 '[저주]' 를 제시 하거나 '대응 기능' 을 제시 합 니 다.
입력 예시:

[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky

출력 샘플
모든 테스트 용례 의 출력 은 한 줄 을 차지 하고 출력 저주 에 대응 하 는 기능 이나 기능 에 대응 하 는 저주 입 니 다.사전 에서 찾 을 수 없 으 면 "what?" 를 출력 합 니 다.
출력 예시:

light the wand
accio
what?
what?

사고 개술.
아주 전형 적 인 문자열 해시 문제
문자열 해시: 문자열 하 시 는 해시 알고리즘 을 이용 한 문자열 압축 방식 으로 문자열 을 롱 롱 롱 형의 숫자 로 압축 할 수 있 으 며, 해시 충돌 이 없 는 상태 에서 해시 알고리즘 을 사용 하면 문자열 의 식별 문 제 를 잘 완성 할 수 있 습 니 다.그러나 문자열 을 식별 할 때 사용 하 는 해시 값 이 같 아야 하기 때문에 해시 알고리즘 은 문자열 의 완전한 일치 문 제 를 계산 할 수 밖 에 없습니다.이 문제 에 사 용 된 해시 알고리즘 은 BKDR 해시 알고리즘 입 니 다. 만약 문자열 의 길이 가 n 이 고 i 위치 에 있 는 문자 가 s [i] 이면 BKDR 해시 알고리즘 은 다음 과 같 습 니 다. H A S H = (a [1] ∗ s e d n + a [2] ∗ s e d n - d - n - 1 +.... + a [n] ∗ s s e e d d 1) HASH = (a [1] * seed ^ n + n + a [1] * * n + a [2]] * seed ^ {n - 1} +...... + a [n] * seed ^ 1] * seed ^ 1) HASH = (a [1]] [1]] * * * * * * seed ^ n +....... seedn + a [2] seedn − 1 +... + a [n]∗ seed 1) 여기 서 주의해 야 할 것 은 제목 이 MOD 의 값 을 정 해 야 한다 면 계산 할 때 나머지 MOD 를 제외 하고 주어진 것 이 없 으 면 일반적으로 1E9 + 7 을 선택해 야 한 다 는 것 이다.공식 적 인 seed 는 일부 질 수 입 니 다. 보통 7, 17, 131 을 가 져 옵 니 다. 주의: 문자열 해시 가 일치 할 때 오류 가 발생 할 수 있 습 니 다. 두 문자열 이 해시 알고리즘 을 사용 하여 계산 한 후에 같은 해시 값 을 얻 으 면 오류 가 발생 할 수 있 습 니 다. 보통 이러한 오 류 를 문자열 해시 충돌 로 만 듭 니 다.비교적 좋 은 해결 방안 은 seed 재 실행 알고리즘 을 바 꾸 는 것 이다.
문제 풀이: 이 문 제 는 [주문 – 해석] 의 하 쉬 가 일치 하 는 것 이다.데 이 터 를 저장 한 후 주문 을 정 하고 해시 알고리즘 을 사용 하여 해시 값 을 계산 하고 해당 하 는 해석 의 index 를 찾 아 표 출력 을 찾 습 니 다.해시 알고리즘 을 사용 하여 해시 값 을 계산 하고 해당 주문 의 index 를 찾 아 표 출력 을 찾 습 니 다.대응 하기 편리 하도록 모든 문자열 그룹 (주문 + 해석) 에 공 통 된 index 를 할당 합 니 다. 주문 과 해석 의 해시 값 은 유일 하 게 index 에 대응 합 니 다.이러한 데이터 구 조 를 구현 하기 위해 맵 저장 (HASH, index) 의 대응 관 계 를 사용 하면 된다.
소스 코드 구현

#include
#include
#include
#include
#include
#include

using namespace std;

const long long mod = 1e9 + 7;
const int seed = 17;
const int M = 1e5 + 5;

map<long long, int> m1;//   
map<long long, int> m2;//   
char r1[M][25];//   
char r2[M][85];//  

int index = 0;
long long hash1 = 0;
long long hash2 = 0;
long long quick_pow(int a, int x)
{
	long long res = 1;
	long long p = a;
	while (x)
	{
		if (x & 1) res = (res * p) % mod;
		p = (p * p) % mod;
		x >>= 1;
	}
	return res;
}
long long make_hash(string s)
{
	long long hash_res = 0;
	for (int i = 0; i < s.size(); i++)
		hash_res += (long long)s[i] * quick_pow(seed, s.size() - i);
	return hash_res;
}
void insert(string s)
{
	string s1, s2;
	for (int i = 1; i < s.size(); i++)
	{
		if (s[i] == ']')
		{
			s1 = s2;
			s2.clear();
			i++;
			continue;
		}
		s2 += s[i];
	}
	hash1 = make_hash(s1);
	hash2 = make_hash(s2);
	strcpy(r1[index], s1.c_str());
	strcpy(r2[index], s2.c_str());
	m1[hash1] = index;
	m2[hash2] = index;
}
void find_ans(string s)
{
	if (s[0] == '[')//      
	{
		string s_new;
		s_new.clear();
		for (int i = 1; i < s.size() - 1; i++)
			s_new += s[i];
		long long hash_num = make_hash(s_new);
		if (m1.count(hash_num) > 0)//   
		{
			int res = m1[hash_num];
			printf("%s
", r2[res]);
		}
		else//   
		{
			printf("what?
");
		}
	}
	else//      
	{
		long long hash_num = make_hash(s);
		if (m2.count(hash_num) > 0)//   
		{
			int res = m2[hash_num];
			printf("%s
", r1[res]);
		}
		else//   
		{
			printf("what?
");
		}
	}
}
int datagroup;
int main()
{
	index = 0;
	datagroup = 0;
	m1.clear();
	m2.clear();

	string s;
	getline(cin, s);
	while (s != "@END@")
	{
		insert(s);
		index++;
		getline(cin, s);
	}
	scanf("%d", &datagroup);
	getchar();
	for (int i = 0; i < datagroup; i++)
	{
		getline(cin, s);
		find_ans(s);
	}
	return 0;

}