백준 BOJ 1893 - 시저 암호

언제나와같이 돌아온 KMP

아주 티어 올리는 맛이 달달한 태그다

 

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

1893번: 시저 암호

지문이 이해하기 그리 쉽지 않은 편인데

간단히 요약해보자면

 

알파벳 순서 표 A를 보고

원문 W를 X칸 이동시키면서 변환한 뒤에,

암호화된 문자열 S에서 변환된 W가 한번만 등장한다면

이때 가능한 모든 X를 찾는 문제이다.

 

문제를 나눠서 생각해보자.

 

1. 순서표 A를 보고 W를 한칸씩 이동시키기.

알파벳과 숫자를 매칭시켜 주는 unordered_map<char,int> 을 사용해서,

순서표 A 안의 문자들을 0 ~ (|A|-1) 범위의 숫자로 바꿔주고,

숫자값을 넣었을때 다시 알파벳을 가져올 수 있도록 char 배열을 사용해서

숫자값에 사칙연산을 적용해서 W를 "시프트" 할 수 있도록 한다

 

unordered_map<char,int> alphnum;
char numalph[256];

int fail[543210];

string shift(string s, int len){
	int N = s.length();
	string ans = "";
	for(int i=0; i<N; i++){
		ans += numalph[(1+alphnum[s[i]])%len];
	}
	return ans;
}

 

2. S에서 W가 한번만 등장하는지 확인하기.

KMP 알고리즘을 통해 해결해 줄 수 있다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;

unordered_map<char,int> alphnum;
char numalph[256];

int fail[543210];

string shift(string s, int len){
	int N = s.length();
	string ans = "";
	for(int i=0; i<N; i++){
		ans += numalph[(1+alphnum[s[i]])%len];
	}
	return ans;
}

void pi(string s){
	memset(fail, 0, sizeof(fail));
	int N = s.length();
	for(int i=1,j=0; i<N; i++){
		while(j>0 && s[i] != s[j]) j = fail[j-1];
		if(s[i] == s[j]) fail[i] = ++j;
	}
	return;
}

int kmp(string s1, string s2){
	int ans = 0;
	pi(s2);
	
	int N = s1.length();
	int M = s2.length();
	
	for(int i=0,j=0; i<N; i++){
		while(j>0 && s1[i] != s2[j]) j = fail[j-1];
		if(s1[i] == s2[j]){
			if(j == M-1){
				ans++;
				j = fail[j];
			}
			else j++;
		}
	}
	
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;
	while(N--){
		memset(numalph, 0, sizeof(numalph));
		alphnum.clear();
		
		string A,W,S;
		cin >> A >> W >> S;
		for(int i=0; i<A.length(); i++){
			numalph[i] = A[i];
			alphnum[A[i]] = i;
		}
		
		vector<int> V;
		int K = A.length();
		
		for(int i=0; i<K; i++){
			if(kmp(S,W) == 1) V.push_back(i);
			W = shift(W, A.length());
		}
		
		if(V.size() == 0){
			cout << "no solution\n";
		}
		if(V.size() == 1){
			cout << "unique: " << V[0] << "\n"; 
		}
		if(V.size() >= 2){
			cout << "ambiguous:";
			for(auto it : V){
				cout << " " << it;
			}
			cout << "\n";
		}
	}
	return 0;
}

구현실수로 잠시 맞왜틀이 있었지만

무사히 AC.