[C++] 3033번 가장 긴 문자열 - 문자열, 해싱, 접미사 배열과 lcp 배열, 라빈-카프

1605번 반복 부분문자열과 똑같은 문제라서 같이 풀이됩니다.

1. 문제

• 알파벳 소문자로 이루어진 길이 L인 문자열의 부분문자열 중, 적어도 한 번은 반복되는 문자열을 '반복 부분문자열'이라고 부르자. 문자열이 주어지면, 가장 긴 '반복 부분문자열'의 길이를 구하는 프로그램을 작성하시오.

<입력>

• -1-   문자열의 길이 L(1≤L≤200,000)이 주어진다.
• -2-   문자열의 이루는 L개의 알파벳 소문자들이 띄어쓰기 없이 주어진다.

<출력>

• -1-   가장 긴 '반복 부분문자열'의 길이를 출력한다. 만약 '반복 부분문자열'이 하나도 존재하지 않는다면 0을 출력한다.

2. 재정의

• 문자열에서 두 번 반복해서 나오는 가장 긴 문자열을 구하시오.

3. 해결 방법

• Suffix Array에서 LCP를 구한다음 LCP[i]중 max값을 구하면 된다.
• <해싱과 이분 탐색, 라빈-카프 알고리즘>
  • 길이가 mid인 공통 부분 문자열이 존재한다고 하자. 그러면 길이가 mid-1인 공통 부분 문자열도 존재한다 .따라서 이분 탐색을 통해 길이가 mid인 공통 부분 문자열이 존재하는지를 확인함으로써 O(lgn)의 계산으로 mid의 최댓값을 구할 수 있다.
  • 길이가 mid인 공통 부분 문자열이 존재하는지를 확인하기 위해서 해싱을 사용한다. 해싱이 같을 경우 두 문자열은 갖다고 인식할 수 있으므로 mid+1부터 시작해서 n-1까지 해싱이 같은 문자열이 있는지 확인한다.
  • 해싱이 같은 문자열이라고 해도 충돌했을 가능성이 있으므로 해싱이 같다면 실제로 두 문자열이 같은지를 확인한다.

4. 실수한 점, 개선할 점

• 위와 같은 해결방법을 사용하면 O(n(lgn)2)의 시간 복잡도를 나타내지만 해싱과 이분 탐색, 라빈-카프 알고리즘을 이용하거나 counting sort로 Manber-Myers Algorithm을 구현하면 O(nlgn)의 시간 복잡도로 코드를 구현할 수 있다.
• 1605번 반복 부분문자열은 해싱과 이분 탐색, 라빈-카프 알고리즘을 통해 해결하고, 3033번 가장 긴 문자열은 Counting Sort로 Manber-Myers Algorithm을 구현함으로써 해결한다.
• Counting Sort로 구현하는 걸 실패해서 다음에 해보려고 한다.

 

<코드>

#include <iostream>
#include <vector>

using namespace std;

//해시 제작을 위한 소수
const int MOD = 100007ll;
const int MAX_N = 200001;

//문자열과 그 길이
char s[MAX_N];
int n;
//특정 해시 값에 해당하는 문자열이 존재하는가?
vector<int> v[MOD];
//최소 공통 부분 문자열이 길이
int ans;

bool cmp(int a, int b, int c) {
    for(int i=0; i<c; i++)
        if(s[i+a] != s[i+b])
            return false;
    return true;
}

void solve() {
    //이분 탐색용 left~right, mid
    int left = 0, right = n-1, mid;
    //해시 제작용 tmp, 해시 값을 빼주는 용도인 거듭제곱 용
    int tmp, p;
    //특정 mid에 해당하는 길이의 공통 부분 문자열이 있는가?
    bool check;
    
    //이분 탐색
    while(left <= right) {
        mid = (left + right)/2;
        tmp = 0, p = 1;
        //0~mid에 해당하는 문자열의 해시 구하기
        for(int i=0; i<mid; i++) {
            tmp = (tmp*2 + s[i]) % MOD;
            p = p*2%MOD;
        }
        
        check = false;
        v[tmp].push_back(0);
        for(int i=mid; i<n; i++) {
            //mid-i+1부터 시작하는 문자열과 그 이전 문자열의 해시 값을 비교
            tmp = (tmp*2 + s[i]) % MOD;
            tmp = (tmp - p*s[i-mid]) % MOD;
            //음수 index 탐지 방지
            if(tmp < 0)
                tmp += MOD;
            //똑같은 해시 값을 가지고 있는 문자열이 있을 경우 적은 확률로 해시가
            //같을 수 있기 때문에 실제로 확인해본다.
            if(!v[tmp].empty()) {
                for(int j=0; j<v[tmp].size(); j++) {
                    //실제로 두 문자열이 같은지 비교
                    if(cmp(v[tmp][j], i-mid+1, mid)) {
                        check = true;
                        break;
                    }
                }
            }
            //이미 길이가 mid인 공통 문자 서열이 존재함을 확인하였으므로
            //더 탐색할 필요가 없음
            if(check)
                break;
            v[tmp].push_back(i - mid + 1);
        }
        
        //이분 탐색
        if(check) {
            ans = max(ans, mid);
            left = mid + 1;
        }
        else
            right = mid - 1;
        
        //v 배열 초기화
        for(int i=0; i<MOD; i++)
            v[i].clear();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> s;
    
    solve();
    
    cout << ans;
    
    return 0;
}

//출처: https://www.acmicpc.net/source/31549360

로그인

풀어야 볼 수 있습니다.

 

<라빈-카프 알고리즘(Rabin-Karp Algorithm)>

https://yjg-lab.tistory.com/218

[알고리즘] 라빈-카프 알고리즘 (Rabin-Karp)

 

<LCP 알고리즘 구현>

https://leyamon.tistory.com/entry/C-9248%EB%B2%88-Suffix-Array-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%A0%91%EB%AF%B8%EC%82%AC-%EB%B0%B0%EC%97%B4%EA%B3%BC-lcp-%EB%B0%B0%EC%97%B4

[C++] 9248번 Suffix Array - 문자열, 접미사 배열과 lcp 배열

 

<실패한 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/6112594

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.