首页 > ACM题库 > HDU-杭电 > Hdu 1734 Power Word 待解决 [解题报告] C++
2013
12-21

Hdu 1734 Power Word 待解决 [解题报告] C++

Power Word

问题描述 :

Recently, loneknight is interesting in investigating the power of word. After several weeks of research, He recognize that there are some magic words in the world, if a word contains a magic word as its substring, it will have magic power. For example, if the word ‘magic’ is magic word, then the word ‘magic’, ‘amagic’, ‘xxmagic’, ‘magiczz’ are all power words.

In addition to this finding, he also find that the index of a powerword has a important impact on the power of word. The index of a power word define as follow: given the set of magic words, if we list all the powerword contain one or more magic word as substring in a list lexicographically from short length to long, the curring position of a word in the list is its index. So, if the magic words are ‘magic’ and ‘hello’, then word have index 1 is ‘hello’, the word have index 2 is ‘magic’, the word have index 3 is ‘ahello’ … (only consider the lowercase words) .

Now, loneknight have find a way to calculate the the indices of the most powerful words, he want to find what the actually word is. Can you help him?

输入:

The input consists of several test cases. Each case contain exactly two line, first line contains the magic words, words are seperated by spaces, the length of each word is at least 1 and at most 5, and the word contain only lowercase characters, the second line contains the indices, indices are seperated by spaces each index in the range [1, 232-1]. (Each line contains at most 10 words or numbers) Your job is to find the powerful word according the indices. The input end with a ling contain "-1".

输出:

For each case, please print the powerful words in a single line seperated by one space without trailing space, according to the order in the input.

样例输入:

hello magic
1 2 3
hello magic
4294967295
hello magic
67 141
-1

样例输出:

hello magic ahello
yskwojhello
magico ahellou


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept