[문자열][시간 초과]HABIT 말장난

1. 완전 탐색

 

이 문제는 주어진 문자열 입력에 대해 

중복된 부분 문자열의 개수를 센다음

k개 이상의 중복 문자열 중에서

가장 긴 부분 문자열을 찾는 문제이다.

 

하지만 부분 문자열을 전부 만들어서

 

카운트하면 시간안에 수행이 불가능하다.

 

2. 공통 접두사의 최대 길이 사용

 

접미사 배열을 만들고 

공통 접두사의 최대 길이를 계산하면 

시간안에 해결할 수 있다.

 

이 때 중요한 것은 k개를 더한것과 비교하는 것이다.

이는 k번째 접미사와 접두사가 일치하지않으면 0이되기 때문에

이는 완활히 작동된다.

 

다음은 책에있는 코드이다.

 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
 
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
 
string strs;
int k;
 
struct Comparator {
    const vector<int>& group;
    int t;
    Comparator(const vector<int>& _group, int _t): group(_group), t(_t) {}
    bool operator ()(int a, int b) {
        if(group[a] != group[b]) return group[a] < group[b];
        return group[a+t] < group[b+t];
    }
};
 
vector<int> getSuffixArray(const string& s)
{
    int n = s.size();
    int t = 1;
    vector<int> group(n+1);
    for(int i = 0; i < n; i++) group[i] = s[i];
    group[n] = -1;
 
    vector<int> perm(n);
    for(int i = 0; i < n; i++) perm[i] = i;
 
    while(t < n)
    {
        Comparator compareUsing2T(group, t);
        sort(perm.begin(), perm.end(), compareUsing2T);
 
        t*=2;
        if(t>=n) break;
 
        vector<int> newGroup(n+1);
        newGroup[n] = -1;
        newGroup[perm[0]] = 0;
 
        for(int i = 1; i < n; i++)
        {
            if(compareUsing2T(perm[i-1], perm[i]))
                newGroup[perm[i]] = newGroup[perm[i-1]] + 1;
            else
                newGroup[perm[i]] = newGroup[perm[i-1]];
        }
        group = newGroup;
    }
    return perm;
}
int commonPrefix(const string& s, int i, int j)
{
    int k = 0;
    int size = s.size();
    while (i < size && j < size && s[i] == s[j])
    {i++; j++; k++;}
    return k;
}
 
int longestFrequent()
{
    int ret = 0;
    vector<int> a = getSuffixArray(strs);
    for(int i = 0; i + k <= a.size(); i++)
        ret = max(ret, commonPrefix(strs, a[i], a[i+k - 1]));
    return ret;
}
 
int main()
{
    int testCase = 0;
    cin>>testCase;
 
    for(int i = 0; i < testCase; i++)
    {
        cin>>k>>strs;
        cout<<longestFrequent()<<"\n";
    }
 
}

 

 

3. 풀면서 실수한것들

 

맨버-마이어스 알고리즘으로 접미사 배열을 생성하는 코드를 짤때

 

새로운 그룹을 만들때 newGroup[perm[i]] 이 아니라 newGroup[i] 로 계산하여 시간초과 되었다.

(예제 입력은 잘작동해서 잘못된지 몰랐다.)

 

또한 새로운 그룹 마지막에 -1 을 추가하는것을 잘 기억해야한다.

 

 

HABIT