首页 > ACM题库 > HDU-杭电 > hdu 2340 Obfuscation[解题报告]hoj
2014
01-05

hdu 2340 Obfuscation[解题报告]hoj

Obfuscation

问题描述 :

It is a well-known fact that if you mix up the letters of a word, while leaving the first and last letters in their places, words still remain readable. For example, the sentence “tihs snetncee mkaes prfecet sesne”, makes perfect sense to most people.

If you remove all spaces from a sentence, it still remains perfectly readable, see for example: “thissentencemakesperfectsense”, however if you combine these two things, first shuffling, then removing spaces, things get hard. The following sentence is harder to decipher: “tihssnetnceemkaesprfecetsesne”.

You’re given a sentence in the last form, together with a dictionary of valid words and are asked to decipher the text.

输入:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with a string s: the sentence to decipher. The sentence consists of lowercase letters and has a length of at least 1 and at most 1 000 characters.

One line with an integer n with 1 ≤ n ≤ 10 000: the number of words in the dictionary.

n lines with one word each. A word consists of lowercase letters and has a length of at least 1 and at most 100 characters. All the words are unique.

输出:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with a string s: the sentence to decipher. The sentence consists of lowercase letters and has a length of at least 1 and at most 1 000 characters.

One line with an integer n with 1 ≤ n ≤ 10 000: the number of words in the dictionary.

n lines with one word each. A word consists of lowercase letters and has a length of at least 1 and at most 100 characters. All the words are unique.

样例输入:

3
tihssnetnceemkaesprfecetsesne
5
makes
perfect
sense
sentence
this
hitehre
2
there
hello
hitehre
3
hi
there
three

样例输出:

this sentence makes perfect sense
impossible
ambiguous

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define HASH_SIZE 1000001
#define INF 1005

using namespace std;
struct NODE {
	int ch[30];
	void clear() { memset(ch, 0, sizeof(ch)); }
	void sp(char c1, char c2) { ch[26]=c1-97, ch[27]=c2-97; }
	int hash()
	{
		int sum=0;
		for (int i=0; i<26; i++) sum=sum*1007+ch[i];
		return ((sum%HASH_SIZE)+HASH_SIZE)%HASH_SIZE;
	}
	bool compare(NODE n)
	{
		for (int i=0; i<28; i++) if (ch[i]!=n.ch[i]) return 0;
		return 1;
	}
}	tmp;

struct HASHTABLE {
	NODE st1[HASH_SIZE];
	int hash[HASH_SIZE], pos[HASH_SIZE], val[HASH_SIZE], id[HASH_SIZE], size;
	int insert(NODE n, int ID)
	{
		int i, now=n.hash();
		for (i=hash[now]; i; i=pos[i]) if (n.compare(st1[i])) return val[i]++, 1;
		return ++size, st1[size]=n, pos[size]=hash[now], hash[now]=size, id[size]=ID, val[size]=1, 0;
	}
	int find(NODE n, int &ID)
	{
		int i, now=n.hash();
		for (i=hash[now]; i; i=pos[i]) if (n.compare(st1[i])) return ID=id[i], val[i];
		return 0;
	}
	void clear() { memset(hash, size=0, sizeof(hash)); }
}	H;

char str[INF], ctr[INF*10][105];
struct NODE2 {
	int x, z, v;
	NODE2() {}
	NODE2(int x, int v, int z):x(x), z(z), v(v) {}
};
vector <NODE2> vec[INF];
int F[INF], Path[INF], ID[INF];

int out(int n)
{
	if (n==0) return 0;
	if (out(Path[n])) printf(" ");
	return printf("%s", ctr[ID[n]]), 1;
}

int main()
{
	int cas, T;

	for (cas=scanf("%d", &T); cas<=T; cas++)
	{
		H.clear();
		scanf("%s", str);
		int n, i, j;
		for (i=0; i<INF; i++) vec[i].clear();
		for (i=scanf("%d", &n); i<=n; i++)
		{
			scanf("%s", ctr[i]);
			for (tmp.clear(), j=0; ctr[i][j]; j++) tmp.ch[ctr[i][j]-97]++, tmp.sp(ctr[i][0], ctr[i][j]);
			H.insert(tmp, i);
		}
		int z, v, len=strlen(str);
		for (i=0; str[i]; i++)
		{
			tmp.clear();
			for (j=i; str[j]; j++)
				if (tmp.ch[str[j]-97]++, tmp.sp(str[i], str[j]), v=H.find(tmp, z), v)
					vec[j].push_back(NODE2(i, v, z));
		}

		memset(F, 0, sizeof(F));
		F[0]=1;
		for (i=1; i<=len; i++)
			for (j=0; j<vec[i-1].size(); j++)
				if (F[vec[i-1][j].x]>0)
				{
					F[i]+=F[vec[i-1][j].x]*vec[i-1][j].v;
					Path[i]=vec[i-1][j].x;
					ID[i]=vec[i-1][j].z;
				}
				
		if (F[len]==0) { puts("impossible"); continue; }
		if (F[len]>1) { puts("ambiguous"); continue; }
		out(len); puts("");
	}
	return 0;
}

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测