[BOJ] 5582 : 공통 부분 문자열

문제 링크

5582번: 공통 부분 문자열 (acmicpc.net)

5582번: 공통 부분 문자열

두 문자열이 가지고 있는 공통 문자열의 최대 길이를 출력하는 문제.

풀이

주어진 문자열을 각각 A, B 라고 하겠다. 나는 A 문자열의 문자를 돌면서 각각을 시작점으로 B 문자열과 비교하는 방식으로 탐색했다. A[0] 부터 A[length - 1] 까지 돌면서 각 문자를 시작점으로 B의 문자열과 비교했다. 모든 A의 문자마다 B문자열 첫 인덱스인 0번째부터 비교를 계속 해나가면 시간이 너무 오래 걸리기 때문에 alpha_st 라는 벡터에 알파벳 순으로 B 문자열에서 해당 알파벳의 인덱스들을 저장해두었다. 

예를 들어 문자열 B를 "AACBDE" 라고 한다면, alpah_st[0] 에는 A의 인덱스인 {0, 1} 을 저장하고, alpha_st[1] 에는 B의 인덱스인 {3}을 저장하고, alpha_st[2] 에는 C의 인덱스인 {2}를 저장해두었다.

그리고 문자열 A를 "CBD" 라고 한다면 A[0]~A[2] 까지 시작점으로 돌게 되는데 A[0]가 시작점인 경우에는 A[0]의 알파벳이 C 이기 때문에 alpha_st[2] 에 들어있는 인덱스를 출발점으로 탐색하면 된다.

int find_max_length(int st) {
	int Max = 0;
	for (int i = 0; i < alpha_st[A[st] - 'A'].size(); i++) {
		int st_idx = alpha_st[A[st] - 'A'][i];
		int Length = 0;
		int A_idx = st;
		for (int j = st_idx; j < B.length(); j++) {
			if (A[A_idx] == B[j]) {
				Length++;
				A_idx++;
			}
			else break;
		}
		Max = max(Length, Max);
	}
	return Max;
}

그렇게 처음에 짠 코드가 이 코드이다. 매개변수 st 자리에는 0 ~ A.length() - 1 의 값이 들어간다.

하지만 이렇게 해도 시간초과가 났다.

그래서 추가해준코드가 아래의 코드이다.

if (B[st_idx + Max] != A[A_idx + Max])
		continue;

 

아이디어를 설명하자면 Max는 현재 공통 문자열의 최대 길이이다. A_idx 는 A의 시작점 인덱스 즉 st 값이고

st_idx는 alpha_st 벡터에서 가져온 B의 시작점이다. 비교하기 전에 공통적인 부분의 길이가 Max보다 크지않다는 걸 미리 안다면 굳이 비교할 필요가 없다. 그래서 B[st_idx + Max] != A[st + Max] 라면 이미 공통적인 문자열 길이가 Max보다 짧다는 뜻이므로 굳이 비교를 하지않고 스킵한다.

예를 들어 A문자열이 "ABCDEABCDE" B 문자열이 "BACEAABDED" 라고 임의로 지정했다.

현재 A문자열에서 4번 인덱스인 'E'를 시작점으로 B 문자열과 비교를 하려한다. alpha_st['E'] 에는 B에서 E의 인덱스인 {3 , 8} 이 들어있다. A는 4번 인덱스를 시작으로 B는 3번 인덱스를 시작으로 비교를 할 것이다. 그런데 현재 찾은 최대 공통 문자열의 길이가 4라고 가정하자. 여기서 A[인덱스 4 + 현재까지 발견된 최대 길이 4] = A[8] . B[인덱스 3 + 현재까지 발견된 최대 길이 4] = B[7]. A[8] 과 B[7]이 다르다면 이미 4보다 긴 공통문자열은 발견이 불가능 한 것이므로 여기서 굳이더이상 비교 하지않고 스킵한다는 의미이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 1000000 + 5;
vector<int> alpha_st[30];
int N;
string A, B;
int ans = 0;
 
void find_max_length(int st) {
    if (st + ans > A.length() - 1)
        return;
    for (int i = 0; i < alpha_st[A[st] - 'A'].size(); i++) {
        int st_idx = alpha_st[A[st] - 'A'][i];
        int Length = 0;
        int A_idx = st;
        if (st_idx + ans > B.length() - 1)
            break;
        if (B[st_idx + ans] != A[A_idx + ans])
            continue;
        for (int j = st_idx; j < B.length(); j++) {
            if (A[A_idx] == B[j]) {
                Length++;
                A_idx++;
            }
            else break;
        }
        ans = max(ans, Length);
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> A;
    cin >> B;
    for (int i = 0; i < B.length(); i++) {
        alpha_st[B[i] - 'A'].push_back(i);
    }
    for (int i = 0; i < A.length(); i++) {
        find_max_length(i);
    }
    cout << ans << "\n";
    return 0;
}
 

설명 능력이 부족해서 아이디어를 글로 적어내는게 어렵다. 아마 내가 나중에 이 글을 다시읽어도 잘 이해하지 못할 것같다. 그래도 코드를 본다면 꾸역꾸역 이해할 수 있을 것이다.