题面：
说无可说(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
样例输入23456
见下发文件
样例输出23456
见下发文件
数据范围
对于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 <cmath> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> 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<lena&&solvedy<lenb)solvedx++,solvedy++; if(solvedx==lena){tempans=min(tempans,dep+lenb-solvedy);return;} if(solvedy==lenb){tempans=min(tempans,dep+lena-solvedx);return;} dfs(solvedx+1,solvedy+1,dep+1); dfs(solvedx+1,solvedy,dep+1); dfs(solvedx,solvedy+1,dep+1); } bool cmp(string &a,string &b){return a.size()>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]); }