[Algospot] Jaeha`s safe (문제 ID : JAEHASAFE)

문제는 책 또는 알고스팟참고

---

KMP 알고리즘을 이용해서 해결한다. 

시계방향으로 돌리는 경우 str[i] + str[i] 와 str[i+1]을 비교해서 똑같아지는 가장 작은 수를 구하면 된다.

반시계방향인 경우 str[i+1] + str[i+1]과 str[i]를 비교한다.

원본 문자열을 두개를 이어 붙여서 비교하는게 핵심 포인트였다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/JAEHASAFE.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int C, N;

vector<int> getPi(const string& str) {
	int m = str.size(), j = 0;
	vector<int> pi(m, 0);
	for (int i = 1; i < m; i++) {
		while (j > 0 && str[i] != str[j])
			j = pi[j - 1];
		if (str[i] == str[j])
			pi[i] = ++j;
	}
	return pi;
}

vector<int> kmp(const string& A, const string& B) {
	int n = A.size(), m = B.size(), j = 0;
	vector<int> res;
	vector<int> pi = getPi(B);
	for (int i = 0; i < n; i++) {
		while (j > 0 && A[i] != B[j])
			j = pi[j - 1];
		if (A[i] == B[j]) {
			if (j == m - 1) res.push_back(i - m + 1);
			else j++;
		}
	}
	return res;
}

int main()
{
	cin >> C;
	while (C--) {
		int res = 0;
		vector<string> str;
		cin >> N;
		string tmp;
		for (int i = 0; i <= N; i++) {			
			cin >> tmp;
			str.push_back(tmp);
		}
		for (int i = 0; i < N; i++) {
			if (i % 2 == 1)
				res += kmp(str[i] + str[i], str[i + 1])[0];
			else
				res += kmp(str[i + 1] + str[i + 1], str[i])[0];
		}
		cout << res << endl;
	}
}