agc047 B

 

 题意：

给一堆字符串

问你有多少个pair，是满足条件的

1 x是y的 后缀

2 x是y 的后缀加上y前面的任意一个字符

题解

开个trie树处理一下

#include<bits/stdc++.h>
//#include<tr1::unordered_map>
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,a,n) for(int i=n;i>=a;--i)
#define pb push_back
#define fi first
#define se second
#define io std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
const int  maxn=1e6+50;
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
ll qpow(ll a,ll n)
{
    ll r=1%P;
    for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P;
    return r;
}
struct node
{
  int a[26];
  int b[26];
};
node tree[maxn];
int pre[maxn];
int cnt;
int ans;
void add(string x)
{ int cur=0;
  int flag=0;
  for(int i=0;i<x.size();i++)
  { 
      int now=x[i]-'a';
      if(!tree[cur].a[now]) {
        tree[cur].a[now]=++cnt;
        pre[cnt]=cur;
      }
      cur=tree[cur].a[now];
  }
  int len=x.size()-1;
  int cntt[26];
  memset(cntt,0,sizeof(cntt));
  while(cur)
  {
        int pe=pre[cur];
        int now=x[len]-'a';
          if(!cntt[now])
          {
            cntt[now]++;
          }
        for(int i=0;i<26;i++)
        {
          if(cntt[i])
            tree[pe].b[i]++;
        }
        cur=pre[cur];
        len--;
  }
}
string a[maxn];
bool cmp(string x,string y)
{
  return x.size()>y.size();
}
int main()
{ io;
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  sort(a+1,a+1+n,cmp);
  for(int i=1;i<=n;i++)
  {
    reverse(a[i].begin(),a[i].end());
    int cur=0;
    int flag=0;
    for(int j=0;j<a[i].size()-1;j++)
      {
        char x=a[i][j];
        int now=x-'a';
        if(!tree[cur].a[now]) {flag=1;break;}
        cur=tree[cur].a[now];
      }
    if(flag) { add(a[i]);continue;}
    int last=a[i].back()-'a';
    ans+=tree[cur].b[last];
    add(a[i]);
  }
  cout<<ans<<endl;
}