[BOJ 26640 // C++] Palindrom

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26640번 문제인 Palindrom이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/26640 

26640번: Palindrom

주어진 문자열의 롤링해시값과 역순 롤링해시값을 구해 둘이 일치한다면 두 문자열을 같은 것으로, 일치하지 않는다면 서로 다른 것으로 생각해 문제를 해결하자.

 

롤링해시를 한 가지 소수가 아닌 복수의 소수들로 계산해 서로 다른 값의 해시값 충돌로 틀릴 확률을 줄일 수 있다.

 

아래는 제출한 소스코드이다.

#define MOD 1000000007
#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll val1[10];
ll val2[10];
char c;
ll p[10] = { 127,131,137,139,149,151,157,163,167,173 }, pp[10] = { 1,1,1,1,1,1,1,1,1,1 };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (cin >> c) {
		for (int k = 0; k < 10; k++) {
			val1[k] = (val1[k] * p[k] + c) % MOD;
			val2[k] = (val2[k] + c * pp[k]) % MOD;
			pp[k] = pp[k] * p[k] % MOD;
		}
	}

	bool chk = 1;
	for (int k = 0; k < 10; k++) {
		if (val1[k] != val2[k]) chk = 0;
	}

	if (chk) cout << "TAK";
	else cout << "NIE";
}