백준 3033 (가장 긴 문자열) c++

문제

3033번: 가장 긴 문자열

길이가 L인 문자열이 주어지면 해당 문자열 안에서 2번이상 등장하는부분문자열 중에서

가장 긴 문자열의 길이를 출력하는 문제입니다.

예를 들어 길이가 11인 문자열 "sabcabcfabc" 이 주어지면 2번이상 등장하는 부분문자열 중에서

가장 긴문자열은 "abc" 이므로 부분문자열 중에서 가장 긴 문자열의 길이는 3입니다.

 

단순히 naive한 풀이를 생각해보면 한 문자씩 반복문을 돌아보며 확인하므로 최대 O(N^2)의 시간복잡도를

가질 수 있습니다.

 

길이가 k인 문자열이 2번이상 등장했다면, k-1 인 문자열도 2번이상 등장할 수 있습니다.

따라서 단조성이 성립되고 parametric search를 생각해 볼 수 있습니다.

 

길이가 n인 문자열에서 두번이상 등장하는 문자열의 길이의 범위는 0~n-1 입니다.

따라서 두번이상 등장하는 문자열의 길이를 m이라 할때 

l = 0, r = n으로 해서 m = (l + r)/2 의 길이로 부분문자열이 중복되는지 확인하면서

binary search방법과 유사하게 최댓값을 갱신해주면 됩니다.

ll l = 0, r = n, mid, ans = -1;
	while (l <= r) {
		mid = (l + r) / 2;
		if (f(mid)) {
			ans = max(ans, mid);
			l = mid + 1;
		}
		else r = mid - 1;
	}
	cout << ans;

 

f 함수가 true라는 의미는 길이가 m인 부분수열이 2번이상 존재한다는 의미입니다.

따라서 l의 길이를 m+1로 설정해주어 m의 길이를 늘려주어 m보다 더 긴 부분수열이 있는지 계속 확인합니다.

const ll p = 26, mod = 200003;
bool f(ll m) {
    ll hash = 0, pw = 1;
    for (int i = 0; i < m; i++)
        hash = (hash * p + s[i]) % mod, pw = (pw * p) % mod;
    vector<ll>v[mod];
    v[hash].push_back(0);
    for (int i = 1; i + m - 1 < n; i++) {
        hash = (hash * p % mod - pw * s[i - 1] % mod + s[i - 1 + m] + mod) % mod;
        for (ll nxt : v[hash]) {
            if (!strncmp(&s[nxt], &s[i], m))return true;
        }
        v[hash].push_back(i);
    }
    return false;
}

해시 자료구조를 활용하였습니다.

해시 테이블(vector v)에는 특수한 hash function을 거쳐 해시 주소 인덱스로 들어가게 됩니다.

 

4, 5 번째 줄을 보면 0번째 글자부터 m-1 번째 글자의 문자열의 해시 주소를 생성하는 것입니다.

예를들어 문자열이 "sabcabcfabc" 이고 m이 3이라면 "sab"의 해시주소가 생성되는 것입니다.

 

7번째 줄을 보시면 이제 "sab"의 해시주소 인덱스에 0을 삽입합니다.

0의 의미는 나중에 hash table에서 충돌이 일어난 위치에서 문자열을 서로 비교할건데 

각 문자열의 처음 비교 인덱스 입니다. 즉, v[hash]에 0이 들어가 있다면 0번째 문자부터 n-1문자 까지 탐색을

하겠다는 의미입니다.

 

8~14 번째 줄을 보면 인덱스 i번째 글자를 포함해 m개의 문자열을 탐색하는 것입니다. (i=1부터 시작)

                                    .

                                    .

                                    .

9번째 줄을 보면 i-1번째 글자는 포함하지 않고 i-1+m 번째 까지의 문자열의 해시주소를 얻는 과정입니다.

 

10번째 줄을 보면 해시 충돌을 의미합니다. 즉, 중복된 부분 수열이 존재한다는 의미입니다.

위의 그림은 해시 주소가 같아서 충돌을 의미합니다.

 

11번째 줄을 보면 strncmp 함수는 문자열 nxt번째 부터 , 문자열 i번째 부터 문자열 끝까지 비교해주면서

m개의 글자가 연속적으로 같으면 0을 return 해주는 함수입니다.

위의 그림을 기준으로 보면 v[hash]에는 이미 1이 존재합니다.

따라서 nxt = 1이 되고 i = 4가 됩니다.

0을 return 하면 m개의 부분 문자열이 존재한다는 의미이므로 true를 return 해줍니다. 

 

13번째 줄을 보면 해시가 충돌하지 않으면 당연히 hash주소에 그대로 i값을 집어넣으면 됩니다.

 

15번째 줄을 보면 해시 충돌이 일어나지 않으면 m의 길이를 가진 중복된 부분문자열이 없다는 의미이므로

그대로 false를 return해주면 됩니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#include<cstdlib>
#include<set>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
string s;
ll n;
const ll p = 26, mod = 200003;
bool f(ll m);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> s;
    n = s.size();
 
    ll l = 0, r = n, mid, ans = -1;
    while (l <= r) {
        mid = (l + r) / 2;
        if (f(mid)) {
            ans = max(ans, mid);
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans;
    return 0;
}
bool f(ll m) {
    ll hash = 0, pw = 1;
    for (int i = 0; i < m; i++)
        hash = (hash * p + s[i]) % mod, pw = (pw * p) % mod;
    vector<ll>v[mod];
    v[hash].push_back(0);
    for (int i = 1; i + m - 1 < n; i++) {
        hash = (hash * p % mod - pw * s[i - 1] % mod + s[i - 1 + m] + mod) % mod;
        for (ll nxt : v[hash]) {
            if (!strncmp(&s[nxt], &s[i], m))return true;
        }
        v[hash].push_back(i);
    }
    return false;
}