Timus #1322 – Pancake's Personal Website

题目：Burrows-Wheeler逆变换，具体读题即可读懂

解析：Burrows-Wheeler 压缩(转换)算法(BWT)。

1. 百度百科上的例子：加列，排序循环

2.我也不知道什么原理，我用的是这种方法。vector of inverse transform.

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

struct BWT
{
	string ch;
	int index;
}bwt[200000];

int f(BWT& a, BWT& b) {
	if (a.ch == b.ch) return a.index < b.index;
	return a.ch < b.ch;
}

int main() {
	int k;
	string line;
	cin >> k >> line;
	int n = line.size();
	for (int i = 0; i < n; i++) {
		bwt[i].index = i;
		bwt[i].ch = line[i];
	}
	sort(bwt, bwt + n, f);
	int temp = k - 1;
	for (int i = 0; i < n; i++) {
		cout << line[bwt[temp].index];
		temp = bwt[temp].index;
	}
	return 0;
}

#include<iostream>

#include<algorithm>

#include<string>

using namespace std;

struct BWT

{

string ch;

int index;

}bwt[200000];

int f(BWT& a, BWT& b) {

if (a.ch == b.ch) return a.index < b.index;

return a.ch < b.ch;

}

int main() {

int k;

string line;

cin >> k >> line;

int n = line.size();

for (int i = 0; i < n; i++) {

bwt[i].index = i;

bwt[i].ch = line[i];

}

sort(bwt, bwt + n, f);

int temp = k - 1;

for (int i = 0; i < n; i++) {

cout << line[bwt[temp].index];

temp = bwt[temp].index;

}

return 0;

}

发表回复 取消回复

发表回复取消回复