字典树板子

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=1e6+10;
string str[N];
struct node{
    int son[26];
    int num;
    bool isend;
}t[N];
int cnt=1;
void Insert(string s){
    int now = 0;
    for(int i=0;i<s.size();i++){
        int ch=s[i]-'a';
        if(t[now].son[ch]==0){
            t[now].son[ch]=cnt++;
        }
        now = t[now].son[ch];
        t[now].num++;
        if(i==s.size()-1) t[now].isend=true;
    }
}
bool mark[N];
int len=0;
int max_len=0;
void dfs(int now,int cnt){
    mark[now]=true;
    if(t[now].isend){
        len=max(cnt,len);
    }
    for(int i=0;i<26;i++){
        if(mark[t[now].son[i]]==false){
            mark[t[now].son[i]]=true;
            dfs(t[now].son[i],cnt+1);
            max_len+=2;
            mark[t[now].son[i]]=false;
        }
    }
}

int n,m;
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        str[i]=s;
        Insert(s);
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        dfs(0,0);
        // cout<<len<<endl;
        // cout<<max_len<<endl;
        cout<<max_len-len<<endl;
    }
    return 0;
}