[Week 4] PALINDROMIZE self review - Choi-mina

[Choi-mina]

PALINDROMIZE self review

• 파일명: PQR/PALINDROMIZE/Choi-mina.cpp
• 수행시간: 228ms

1. 고민 과정

KMP을 사용해서 풀어야 한다는 것은 알고 있었는데 KMP를 이해하는게 어려웠습니다.

2. 풀이 아이디어

KMP개념을 이해하기 위해 스터디 시간에 사용한 자료와 종만북을 참고해 개념을 공부하였습니다.
겹치는 부분을 찾고 원래 문자열과 뒤집은 문자열을 더한 후 겹치는만큼 빼주어 결과를 구할 수 있었습니다.

3. 작성한 코드와 설명

vector <int> match(const string &rs) {
	vector<int> pi(rs.size(), 0);
	int begin = 1, matched = 0;

	while (begin + matched < rs.size()) {
		// begin+matched에 있는 문자와 matched에 있는 문자가 같은 경우
		if (rs[begin + matched] == rs[matched]) {
			++matched;
			pi[begin + matched - 1] = matched;
		}
		// 다른 경우
		else {
			// matched가 0인 경우에는 다음칸부터 계속해서 계산
			if (matched == 0)
				++begin;
			else {
				// 시작위치를 (matched - 일치하는 접두사와 접미사가 길이)만큼 빼서 이동
				begin += matched - pi[matched - 1];
				// begin을 옮기고 나서도 pi[matched - 1]만큼은 같으니까
				// matched = pi[matched - 1]
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

match() 함수는 부분 일치 테이블 계산 함수입니다.
vector로 만든 pi에 접미사도 되면서 접두사도 되는 문자열의 최대길이를 넣어놓고 마지막에 반환을 해줬습니다.

int palindrome(const string &s, const string &rs) {
	vector <int> pi = match(rs);
	int m = s.size(), n = rs.size();
	int begin = 0, matched = 0;
	
	while (begin < n) {
		// s의 글자가 rs의 글자와 같은 경우
		if (s[begin + matched] == rs[matched]) {
			++matched;
			
			// 마지막 문자까지 다 보고 겹치는 부분의 길이 반환
			if (begin + matched == n)
				return matched;
		}
		// 두 글자가 같지 않은 경우
		else {
			// matched가 0인 경우에는 다음칸부터 계속해서 계산
			if (matched == 0)
				++begin;
			else {
				// 시작위치를 (matched - 일치하는 접두사와 접미사가 길이)만큼 빼서 이동
				begin += matched - pi[matched - 1];
				// begin을 옮기고 나서도 pi[matched - 1]만큼은 같으니까
				// matched = pi[matched - 1]
				matched = pi[matched - 1];
			}
		}
	}
	return 0;
}

palindrome()함수는 s의 접미사이면서 rs의 접두사인 문자열의 최대 길이를 구하는 함수입니다.

int main() {
	cin >> C;

	for (int i = 0; i < C; i++) {
		string S, reverseS;
		cin >> S;

		for (int j = S.size() - 1; j >= 0; j--)
			reverseS += S[j];

		cout << S.size() * 2 - palindrome(S, reverseS) << endl;
	}

	return 0;
}

원래 문장의 길이와 뒤집은 문장의 길이를 더해주고 겹치는 부분을 빼면 되는데 길이는 똑같기 때문에 원래 문장을 2배 해주었습니다. palindrome에서 반환받은게 겹치는 길이이기 때문에 이를 빼주어 답을 구할 수 있습니다.