#6182. 说无可说

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

沉默之中,我已不懂言语。
幻觉中,有人在轻声低吟。
那是谁?
我听见,那个人说了 N 句话,然而好多话都是重复或者类似,比沉默更加让人不堪。
打破不堪,我想。
每句话是由若干个小写字母组成的字符串。
字符串 A B 的相似度定义如下:
字符串 A 通过以下三种操作:

  1. 插入一个字符;
  2. 删除一个字符;
  3. 替换一个字符。

变成字符串 B 的最少操作次数。
比如字符串 abcd 变成 ccd 的最少次数是 2
首先,删掉字符 a 得到 bcd,然后,将 b 变成 c,得到 ccd
给出 N 个字符串,求出相似度分别为 1,2,3,4,5,6,7,8 的字符串对数。

输入格式

第一行一个正整数 N
接下来 N 行,每行一个字符串。

输出格式

一行输出八个数,表示相似度分别为 1,2,3,4,5,6,7,8 的字符串对数。

样例

样例输入 1

5
asxglhxpjdczgmt
sxflkxppkcztnmt
sxglkxpjdzlmt
xglkxxepjdazelmzc
asxglkqmvjddalm

样例输出 1

0 0 0 1 0 1 3 1

样例输入 2, 3, 4, 5, 6

见附加文件

样例输出 2, 3, 4, 5, 6

见附加文件

数据范围与提示

对于 10\% 的数据, 1 \leq n \leq 20 1 \leq 每个字符串的长度 \leq 12
对于 30\% 的数据,字符串的总长度 \leq 5000
对于 40\% 的数据,字符串的总长度 \leq 12000
对于 60\% 的数据,字符串的总长度 \leq 100000
对于另外 20\% 的数据, 1\leq n \leq70
对于 100\% 的数据, 1 \leq n \leq 200 ,字符串的总长度 \leq 1000000

鸣谢 WerKeyTom_FTD 的神犇同学 Samjia2000 授权本 OJ 独家拥有在线测评使用权。