题面：

说无可说(say.pas/cpp/c)

题目描述

“What’s left to say when every word’s been spoken?”

“若沉默再无休止，是否已经说无可说？”

------来自网易云音乐<Golden Leaves-Passenger>

沉默之中，我已不懂言语。

幻觉中，有人在轻声低吟。

那是谁？

我听见，那个人说了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<=n<=20，1<=每个字符串的长度<=12

对于30%的数据，字符串的总长度<=5000

对于40%的数据，字符串的总长度<=12000

对于60%的数据，字符串的总长度<=100000

对于另外20%的数据，1<=n<=70

对于100%的数据，1<=n<=200，字符串的总长度<=1000000

思路：

DFS

别问我复杂度

反正我卡不掉

解题报告：

say

“对于30%的数据，字符串的总长度<=5000”

DP，枚举两个串A和B，设f[i][j]表示A中以第i位开始的字符串变成B中以第j为开始的字符串的最小次数

“对于40%的数据，字符串的总长度<=12000”

跟30%的一样，数组滚动就好了。

“对于60%的数据，字符串的总长度<=100000”

所以DP时很多状态都是无用的，因为如果两个串的长度差大于8那么对答案没有贡献

“对于另外20%的数据，1<=n<=70”

其实这档跟正解没有什么区别，好像也是可以过掉100分的，没有实测，但是分分钟跑的比正解快？！

由于只要求相似度小于等于8 的字符串对数，那么考虑递归的计算两个串的相似度，对于串A和B，假设当前我们已经匹配到x和y（x是A中的位置,y是B中的位置），那么首先跳过以这两个位置开头的LCS，然后三种操作继续递归下去，如果答案大于8就退出。

求LCS的时候就用hash+二分

“对于100%的数据，1<=n<=200，字符串的总长度<=1000000”

其实我也不是很懂，怎么玄学就跑过去了呢？std的做法是...跳LCS的时候一个个跳...详情见标程...不要打我...wo shi la ji

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int n,k,lena,lenb,tempans,ans[10];char a[1000500],b[1000500];string str[205];void dfs(int solvedx,int solvedy,int dep){ if(dep+abs((lena-solvedx)-(lenb-solvedy))>=tempans)return; while(a[solvedx]==b[solvedy]&&solvedx
           
            
             b.size();}int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)cin>>str[i]; sort(str+1,str+1+n,cmp); for(int i=1;i<=n;i++){ strcpy(a,str[i].c_str()); lena=strlen(a); for(int j=i+1;j<=n;j++){ if(abs((int)str[j].size()-(int)str[i].size())<9){ strcpy(b,str[j].c_str()); lenb=strlen(b); tempans=9; dfs(0,0,0); ans[tempans]++; } } } for(int i=1;i<=8;i++)printf("%d ",ans[i]);}