在m组数，每组有n个数（数的范围1-n）中，找到某些序列 使它是每组数的一个公共子序列，问这样的某些序列的个数？
1≤n≤100000 , 1≤m≤10

公共子串：1 2 3 23一共4个。

思考：我当时想的是暴力搜索一遍,找到1，2序列的公共子串(长度>1)在去3~n序列搜索
例如：
5 2
1 2 3 4 5
1 5 2 3 4
找到了234，因为单独的一个数组肯定是一个公共子串，所以只考虑>1的公共子串计数
对234长度为2的公共子串为2， 长度为3为1
那么一共有5 + 2 + 1=8
对长度为n的公共子串有(n-1)+(n-2)+(n-3)+…+1

看复杂度好像是可行的，最大O(nm)，但是比较难写。

看了大佬的题解，果然用了一个方法比较快速又方便的方法找到n个字符串的公共子串

创立一个next数组，使每组中第i个数的next 是第i+1个数，即 nex[ a[i] ] = a[ i+1 ] （实际上设next是二维数组）。对第一组中的第i个数，如果在其余每组的next[ a[ i -1] ]都是等于第一组中a[ i ]的，意味着序列 a[ i-1 ],a[ i ]是一个公共子序列

这个方法太神了，因为可以在复杂度为O(1)的情况下，找到其他串应该和这个字符匹配的位置，看不懂的自己慢慢理解。

利用一个数组 d[ ]，d[ i ]记做 第 i 个数到第1个数之间满足条件的子序列的个数 。对 i ，如果满足条件，是公共子序列的话，d[ i ]=d[ i-1 ] + d[ i ]，当然初始的时候 d[ i ] =1 （因为单独的一个数组肯定是一个公共子串，题目一定满足）。

这个d[i]可以扩展一下：
如果第i个字符匹配假设长度为n
对长度为n的公共子串有(n)+(n-1)+(n-2)+…+1（单个数计入）

那么如果i+1个字符也匹配，长度为n+1
(n+1)+(n)+(n-1)+…+1
所以增加了（n+1）

因为d[i]=n，上面定义，d[i+1]+=d[i]，所以d[i+1]=n+1正好为增加的公共子串，所以把所有的d[]相加就是答案，而且d[]的最大值就为最长的公共公共子串，还可以想想什么时候d[]初始化为0

思考：用了一节大物课学了个神仙套路，赚了

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=100005;

int n,m,a[11][N];
int nex[11][N];
ll d[N];

int main()
{
    a[1][0]=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
         for(int j=1;j<=n;j++)
         {
             scanf("%d",&a[i][j]);
             nex[i][a[i][j-1]]=a[i][j];
         }
     }

     d[1]=1;
     for(int i=2;i<=n;i++)
     {
         int x=a[1][i-1];
         int flag=0;
         d[i]=1;
         for(int j=2;j<=m;j++)
         {
             if(a[1][i] != nex[j][x] ){
                 flag=1; break;
             }
         }
         if(!flag) d[i]+= d[i-1];
     }

     ll ans=0;

     for(int i=1;i<=n;i++)
     {
         ans+=d[i];
     }
     cout<<ans<<' '<<*max_element(d+1, d+n+1)<<endl;
}
/*

5 6
1 2 3 4 5
2 3 1 4 5
3 4 5 1 2
3 5 4 2 1
2 3 5 4 1
1 2 3 4 5

*/