【题意】：给你m个长度为n的排列，m<=10，n<=100000，让你求有多少种不同的公共子串。
【题解】：就目前而言，如果是在多个字符串中求不同的公共子串个数，还不是一个能在较低复杂度下就能解决的问题，所以这道题一定是有它自己特殊的地方：排列（permutaion）。因为是排列，那么每一个数字只会出现一次，那我们就能记录每一个字符串中每一个数字后面跟着的是谁，那么判断是否存在某个子串的时候，只要O(1)的时间就可以知道是不是存在。
比如，判断1 2是否是所有串的公共子串。那么我们首先应该判断好1已经是所有串的公共子串，因为一个串如果是所有串的公共子串，那它的任何子串也都必须是所有串的公共子串。那么我们在每个串中用O(1)的时间判断一下1后面跟着的是不是2即可。
所以我们可以在第一个串中尺取。如果当前数字满足条件，右指针往右走，不满足的时候 左指针到右指针，右指针不动，并且ans+=len*（len+1）/2，len是当前的串长度，即r-l+1。
【代码】：
#include<bits/stdc++.h> using namespace std; typedef long long ll; int num[15][100000+10]; int hou[15][100000+10]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ scanf("%d",&num[i][j]); if(j>0) hou[i][num[i][j-1]]=num[i][j]; } } if(m==1){ ll ans=(ll)n*(n+1)/2; return 0*printf("%lld\n",ans); } ll ans=0; int l=0,r=0,len=0,be=0; for(;r<n;r++){ //printf("%d %d\n",l,r); if(l==r){ len=1; be=r; } else{ int flag=0; for(int j=1;j<m;j++){ if(hou[j][num[0][be]]!=num[0][r]){ flag=1; break; } } if(flag==0){ be=r; len++; } else{ ans+=(ll)len*(len+1)/2; len=0; l=r; r--; } } } if(len){ ans+=(ll)len*(len+1)/2; } printf("%lld\n",ans); return 0; }
