CF590E.Birthday

NOI/NOI+/CTSC

通过率:0%

时间限制:3.00s

内存限制:512MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Today is birthday of a Little Dasha — she is now 8 years old! On this occasion, each of her n friends and relatives gave her a ribbon with a greeting written on it, and, as it turned out, all the greetings are different. Dasha gathered all the ribbons and decided to throw away some of them in order to make the remaining set stylish. The birthday girl considers a set of ribbons stylish if no greeting written on some ribbon is a substring of another greeting written on some other ribbon. Let us recall that the substring of the string s is a continuous segment of s.

Help Dasha to keep as many ribbons as possible, so that she could brag about them to all of her friends. Dasha cannot rotate or flip ribbons, that is, each greeting can be read in a single way given in the input.

今天是小达莎的生日——她现在8岁了!为此,她的 nn 位朋友和亲戚每人送给她一条写有祝福语的丝带,结果发现所有祝福语各不相同。达莎把所有丝带收集起来,决定扔掉其中一部分,以使剩余的丝带集合显得“时尚”。这位寿星认为,一个丝带集合是“时尚”的,当且仅当其中任意一条丝带上写的祝福语都不是另一条丝带上祝福语的子串。我们回顾一下:字符串 ss 的子串是指 ss 中一段连续的字符序列。

请帮助达莎保留尽可能多的丝带,以便她能向所有朋友炫耀。达莎不能旋转或翻转丝带,也就是说,每条丝带上的祝福语只能按输入中给出的方式阅读。

输入格式

The first line of the input contains integer n (1 ≤ n ≤ 750) — the number of Dasha's relatives and friends.

Each of the next n lines contains exactly one greeting. Each greeting consists of characters 'a' and 'b' only.

The total length of all greetings won't exceed 10 000 000 characters.

输入的第一行包含一个整数 nn(1≤n≤7501 \leq n \leq 750)——表示达莎的亲戚和朋友的数量。

接下来的 nn 行中,每行恰好包含一条问候语。每条问候语仅由字符 'a' 和 'b' 组成。

所有问候语的总长度不超过 10 000 00010\,000\,000 个字符。

输出格式

In the first line print the maximum size of the stylish set. In the second line print the numbers of ribbons involved in it, assuming that they are numbered from 1 to n in the order they appear in the input. If there are several stylish sets of the maximum size, print any of them.

第一行输出时尚集合的最大大小。
第二行输出参与该集合的丝带编号,假设这些丝带按输入顺序从 1 到 nn 编号。如果存在多个最大大小的时尚集合,输出其中任意一个即可。

输入输出样例

  • 输入#1

    5
    abab
    aba
    aabab
    ababb
    bab

    输出#1

    2
    2 5

说明/提示

In the sample, the answer that keeps ribbons 3 and 4 is also considered correct.

在样例中,保留丝带 3 和 4 的答案也被视为正确。

输入解题思路,AI测评打分。不知道怎么写?

首页