QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 256 MB Total points: 100

#2106. Druk

الإحصائيات

印刷工 Bajtazar 接到了一项任务,需要打印一块写有文本的牌子。牌子上的字母均匀地排列在一个大小为 $n \times m$ 的网格上。Bajtazar 将使用印刷模板来完成打印,该模板是一个宽度等于一行字母宽度的条带。打印过程是通过(可能多次)将模板贴在牌子上方并在模板正上方喷洒油墨完成的,同时在打印时模板不能超出牌子的边界。

模板将准备为横向纵向两个版本,并且两个版本必须包含完全相同的文本。牌子上的每一个位置,Bajtazar 都必须且只能用模板打印一次。注意,任意一个模板版本都不能被旋转,否则字母将会被旋转打印。

请你帮助 Bajtazar,给出所有可能的模板长度,使得 Bajtazar 能够打印完整块牌子。

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$,分别表示牌子上的行数以及每一行中的字母数量。

接下来的 $n$ 行中,第 $i$ 行包含一个长度为 $m$ 的字符串,由小写英文字母(a–z)组成,表示牌子上从上往下数第 $i$ 行的目标内容。

输出格式

输出的第一行应包含一个整数,表示 Bajtazar 可以用来打印牌子的模板长度数量。

第二行应包含所有这些长度,按严格递增顺序排列,并用单个空格分隔。

如果第一行输出的是数字 0,则第二行应保持为空。

样例数据

对于如下输入数据:

5 8
aabaaaaa
babaabbb
aabaaaaa
aabaaaaa
abaaabaa

正确的输出为:

1
4

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试数据组成。

子任务 条件 分值
1 $n = 1,\ m \le 1000$ 10
2 $n \le 3,\ m \le 1000$ 25
3 $n, m \le 20$ 20
4 $n, m \le 1000$ 45

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.