Demo entry 6746705

Sardinas–Patterson algorithm

   

Submitted by anonymous on May 30, 2018 at 17:56
Language: C++. Code size: 2.8 kB.

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

//码元数量
const int max_size = 2;
//最大码字长度
const int max_len = 100;
const int max_node = 1000;
//后缀数组记录表
set<string> table;
void dfs(int id, string s, int state);
struct Trie {
	int ch[max_node][max_size];
	int val[max_node];
	int size;
	int idx(char c) {
		return c - '0';
	}
	void init() {
		size = 1;
		memset(ch[0], 0, sizeof(ch[0]));
	}
	//插入建树过程
	int insert(string s, int v) {
		int u = 0, n = s.length();
		int flag = 1;
		vector<int> vec;
		for (int i = 0; i<n; i++) {
			int c = idx(s[i]);
			if (!ch[u][c]) {
				memset(ch[size], 0, sizeof(ch[size]));
				val[size] = 0;
				ch[u][c] = size++;
			}
			if (val[u] == 1 && v == -1) {
				vec.push_back(u);
			}
			u = ch[u][c];
		}
		for (int i = 0; i<vec.size(); i++) {

			dfs(vec[i], "", -1);
		}
		if (val[u] == 1)
			flag = -1;
		val[u] = v;
		return flag * u;
	}
}Tree;

//判断是否有码字重合

bool same = false;

int len;

//从当前节点遍历树,找出所有后缀数组

void dfs(int id, string s, int state) {
	if (same)
		return;

	bool none = true;
	for (int i = 0; i<max_size; i++) {
		if (Tree.ch[id][i]) {
			none = false;
			break;
		}
	}

	//插入后缀数组字符
	if (state == -1 && Tree.val[id] == -1) {
		if (table.find(s) == table.end()) {
			int x = Tree.insert(s, -1);
			if (x<0) {
				same = true;
				return;
			}
			table.insert(s);
			dfs(x, "", 1);
		}
	}



	if (state == 1 && Tree.val[id] == 1) {

		int x = -2;
		if (s != ""&&table.find(s) == table.end()) {
			x = Tree.insert(s, -1);
			table.insert(s);
			if (x<0) {
				same = true;
				cout << endl << "same  " << s << endl << endl;
				return;
			}
			dfs(x, "", 1);
		}
	}
	if (none)
		return;
	//向树的下一层搜索
	for (int i = 0; i<max_size; i++) {
		if (Tree.ch[id][i]) {
			char temp = '0' + i;
			dfs(Tree.ch[id][i], s + temp, 1);
		}
	}
}
//记录总码字
string list[max_len];
int pos[max_len];

int ReadDataFromFileLBLIntoCharArray()
{
	ifstream fin("input.txt");
	const int LINE_LENGTH = 100;
	char str[LINE_LENGTH];
	string s;
	int i = 0;
	Tree.init();
	cout << "building tree" << endl;
	//文件读入
	while (fin.getline(str, LINE_LENGTH))
	{
		list[i] = str;
		pos[i] = Tree.insert(list[i], 1);
		i++;
		cout << "NO." << i << "  :" << pos[i - 1] << " " << list[i - 1] << endl;
	}
	return i;
}


int main()
{

	int len;
	len = ReadDataFromFileLBLIntoCharArray();
	for (int i = 0; i<len && !same; i++) {
		dfs(pos[i], "", 1);
	}
	if (same)
		cout << "NO" << endl;
	else {
		cout << "YES" << endl;
	}
	set<string>::iterator iter;
	for (iter = table.begin(); iter != table.end(); iter++) {
		cout << *iter << endl;
	}

	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).