A182172.Yuilice 的滚筒标签
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
题目描述
Yuilice 的标签机中有 n 行标签,从上到下编号为 1 到 n。每行标签都是一个长度为 m、只含小写英文字母的字符串,第 i 行记为 si。
她需要选择一个整数 k,满足 0≤k<m,然后将所有字符串同时向左循环移动 k 位。具体来说,将一个字符串开头的 k 个字符按原顺序移到末尾;当 k=0 时,字符串不变。所有行必须使用相同的 k,行与行之间不能交换位置。
移动完成后,Yuilice 希望这些字符串按从上到下的顺序,满足字典序非降,即每一行都不大于下一行。两个等长字符串比较字典序时,从左到右找到第一处不同的字符,字母较小的一方字典序较小;如果没有不同字符,则两个字符串相等。
请计算有多少个不同的整数 k 满足要求。即使两个不同的 k 得到的全部字符串恰好相同,它们仍算作两种选择。
输入格式
第一行包含两个整数 n,m,分别表示标签行数和每行字符串的长度。
接下来 n 行,第 i 行包含一个长度为 m 的字符串 si,表示第 i 行标签的内容。字符串只含小写英文字母。
输出格式
输出一行一个整数,表示合法的整数 k 的数量。没有合法选择时输出 0。
输入输出样例
输入#1
3 4 abca abcb abda
输出#1
3
输入#2
2 3 aba aba
输出#2
3
说明/提示
样例解释
样例 #1 中,k=0、k=1、k=2 均合法。例如,k=2 时,三行依次为 caab、cbab、daab,满足字典序非降。
当 k=3 时,三行依次为 aabc、babc、aabd,第二行大于第三行,因此不合法。答案为 3。
样例 #2 中,两行内容相同。无论选择 k=0、k=1 还是 k=2,移动后两行仍然相等,因此三种选择都合法。
数据范围
对于所有测试数据,满足 1≤n,m≤106,n×m≤106。所有字符串长度均为 m,且只含小写英文字母。
| 测试点编号 | n | m | n×m |
|---|---|---|---|
| 1∼4 | 1≤n≤2000 | 1≤m≤2000 | n×m≤2000 |
| 5∼20 | 1≤n≤106 | 1≤m≤106 | n×m≤106 |
输入解题思路,AI测评打分。不知道怎么写?