cf-edu-142.D

题目链接：https://codeforces.com/problemset/problem/1792/D

算法：tire树求最长公共前缀(lcp)。

反思：题目转换出的题意已大致得到，但怎么具体求不会。

思路：tire树维护一个结构，1在哪些位置出现，2在哪些位置出现，以此类推。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int tr[N*15][15],idx;
vector<int>num[N];
int temp[15],n,k;
void add(){
    int h = 0;
    for (int i=1;i<=k;i++){
        if (!tr[h][temp[i]]) tr[h][temp[i]] = ++idx;
        h = tr[h][temp[i]];
    }
}
int query(vector<int> t){
    int h = 0;
    int ans = 0;
    for (int i=0;i<t.size();i++){
        if (tr[h][t[i]]){
            ans++;
            h = tr[h][t[i]];
        }else break;
    }
    return ans;
}
void solve(){
    cin>>n>>k;
    idx = 0;
    for (int i=0;i<=n*k;i++){
        for (int j=1;j<=10;j++) tr[i][j] = 0;
    }
    for (int i=1;i<=n;i++) num[i].clear();
    for (int i=1;i<=n;i++){
        int last = 0;
        for (int j=1;j<=k;j++){
            int x;
            cin>>x;
            num[i].push_back(x);
            temp[x] = j;
        }
        add();
    }
    for (int i=1;i<=n;i++){
        cout<<query(num[i])<<' ';
    }
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    T = 1;
    cin>>T;
    while(T--) solve();
    return 0;
}