post list

2015년 7월 10일

[Algorithm] LCP

#include <iostream>
#include <stdio.h>

using namespace std;
char tstr[5005];
int idxarr[5005];
int LCP[5005];
int LEN[5005];
long long int noval;

void swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
}

int strlen(char* chr)
{
int len = 0;
while(chr[len++] != '\0');
return len - 1;
}

int scmp(char ch1[], char ch2[])
{
int i = 0; int len1 = strlen(ch1);
int j = 0; int len2 = strlen(ch2);
while(i < len1 && j < len2){
if(ch1[i] < ch2[j]) return 1;
else if(ch1[i] > ch2[j]) return 0;
i++; j++;
}
return len1 < len2 ? 1 : 0;
}

void init(int n)
{
for(int i=1; i<=n; i++){
idxarr[i] = i;
LCP[i] = 0;
LEN[i] = 0;
}
noval = 0;
}

int partition(int arr[], int left, int right)
{
int low = left;
int high = right + 1;
int ppos = left;
char* pval = tstr + arr[ppos];

do{
do low++;
while (low < right && !(scmp(pval, tstr + arr[low])));
do high--;
while (left < high && (scmp(pval, tstr + arr[high])));
if(low < high) swap(arr[low],arr[high]);
}while(low < high);
swap(arr[ppos],arr[high]);
return high;
}

void sortarr(int arr[], int left, int right)
{
if(left < right) {
int pivot = partition(arr, left, right);
sortarr(arr, left, pivot - 1);
sortarr(arr, pivot + 1, right);
}
}

void makelen(int n)
{
for(int i=1; i<=n; i++)
noval += (LEN[i] = strlen(tstr + idxarr[i]));
}

void makelcp(int n)
{
for(int i=2; i<=n; i++){
int len1 = strlen(tstr + idxarr[i-1]);
int len2 = strlen(tstr + idxarr[i]);
int len = len1 < len2 ? len1 : len2;
for(int j=0; j<len; j++){
if ((tstr + idxarr[i - 1])[j] == (tstr + idxarr[i])[j])
noval -= ++LCP[i];
else break;
}
}
}

char sol[5005];
void printsol(int t, int n, int k)
{
if(noval < k){
printf("#%d none\n",t);
return;
}
int cnt = k;
int iter = 1;
while(true){
int tmp = cnt;
tmp -= (LEN[iter] - LCP[iter]);
if(tmp <= 0)
break;
cnt -= (LEN[iter] - LCP[iter]);
iter++;
}
for(int i=0; i<cnt + LCP[iter]; i++){
sol[i] = (tstr + idxarr[iter])[i];
}
sol[cnt + LCP[iter]] = '\0';
printf("#%d %s\n",t, sol);
}

int main()
{
//freopen("sample_input.txt","r",stdin);
for(int t=1; t<=40; t++){
int K; cin >> K >> (tstr + 1);
int len = strlen(tstr + 1);
init(len);
sortarr(idxarr, 1, len);
makelcp(len);
makelen(len);
printsol(t, len, K);
}
return 0;
}

댓글 없음:

댓글 쓰기