Boj 1893) 시저 암호

문제

백준 1893

설명

알파벳의 갯수가 최대 62개라서 쉬프트 연산을 하나씩 해도 상관은 없다. 하지만 나는 비슷한 문제를 보고 온 뒤라서 문자간의 알파벳번호 차이를 이용해서 한번에 KMP 를 돌려 해결하고자 했다.

방법은 간단하다. 바로 앞 문자와의 알파벳 번호 차이를 저장해서 KMP 로 돌린다, 그러면 매칭된 패턴의 첫번째에 해당되는 문자와 W 의 첫글자 간의 차이는 몇번 쉬프트 해야 되는지를 의미하게 된다. 이때 여러번 매칭될 수 있는데, 같은 첫글자가 (곧 같은 쉬프트 횟수가) 여러개 존재하면 원문이 여러번 등장한다는 의미가 되므로 오직 한번만 해당되는 경우만 세면 된다.

구현에 주의사항이 몇가지가 있다.

• 문자간의 차이는 \(\vert \mathrm{A} \vert\) 로 모듈러처리를 해준다.
• \(\vert \mathrm{W} \vert\) 가 1인 경우는 알파벳 번호의 차이를 구할 수 없으므로 예외처리 해준다.
• KMP 에서 쓰이는 failTB[] 는 초기화를 꼭 해준다.

시간 복잡도

O(\(\vert \mathrm{W} \vert + \vert \mathrm{S} \vert\))

코드

int failTB[50001];
int src[50001], txt[500001];
int c2i[256];

int main()
{
	fastio;
	int t; cin >> t;
	while (t--)
	{
		string a, b, c;
		cin >> a >> b >> c;
		for (int i = 0; i < a.size(); i++) c2i[a[i]] = i;
		for (int i = 0; i < b.size() - 1; i++)
			if ((src[i] = c2i[b[i + 1]] - c2i[b[i]]) < 0) // 모듈러 연산이 비싸서 덧셈으로 대체
				src[i] += a.size();
		for (int i = 0; i < c.size() - 1; i++)
			if ((txt[i] = c2i[c[i + 1]] - c2i[c[i]]) < 0)
				txt[i] += a.size();


		vector<int> checks(100);
		if (b.size() == 1) // 빼먹기 쉬운 부분
		{
			for (auto i : c) 
				checks[c2i[i]]++;
		}
		else {
			for (int i = 1, j = 0; i < b.size() - 1; i++)
			{
				while (j > 0 && src[i] != src[j]) j = failTB[j - 1];
				if (src[i] == src[j]) failTB[i] = ++j;
				else failTB[i] = 0;   // 빼먹기 쉬운 부분
			}
	
			for (int i = 0, j = 0; i < c.size() - 1; i++)
			{
				while (j > 0 && txt[i] != src[j]) j = failTB[j - 1];
				if (txt[i] == src[j]) {
					if (j == b.size() - 2) {
						checks[c2i[c[i - j]]]++;
						j = failTB[j];
					}
					else j++;
				}
			}
		}
	
		vector<int> ans;
		for (int i = 0; i < 100; i++)
			if (checks[i] == 1)
				ans.push_back((i - c2i[b[0]] + a.size()) % a.size());
	
		if (ans.size() == 0) cout << "no solution\n";
		else {
			sort(ans.begin(), ans.end());
			cout << (ans.size() == 1 ? "unique: " : "ambiguous: ");
			for (auto aaa : ans)
				cout << aaa << ' ';
			cout << '\n';
		}
	}
}