AC自动机调吐了求助!!
查看原帖
AC自动机调吐了求助!!
210719
Violet___Evergarden楼主2021/7/19 12:03
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int kMaxN=1e6+1;


struct TRIE
{
  int son[26];
  int nt,flag;
}t[kMaxN];
int n,cnt;


char a[kMaxN];


int que[kMaxN*2],hd=1,ta=1;
void ins(char *a)
{
  int la=strlen(a),now=1;
  for(int i=0;i<la;i++)
  {
    int k=a[i]-'a';
    if(t[now].son[k]==0)
    {
      cnt++;
      t[now].son[k]=cnt;
    }
    now=t[now].son[k];
  }
  t[now].flag++;
}
void g()
{
  for(int i=0;i<=25;i++)
  {
    t[0].son[i]=1;
  }
  que[ta]=1;
  t[1].nt=0;
  while(hd<=ta)
  {
    int k=que[hd];
    for(int i=0;i<=25;i++)
    {
      int di=t[k].son[i],ff=t[k].nt;
      if(di==0)
      {
        t[k].son[i]=t[ff].son[i];
        continue;
      }
      t[di].nt=t[ff].son[i];
      que[++ta]=di;
    }
    hd++;
  }
}
int walk(char *a)
{
  int now=1,ans=0,la=strlen(a);
  for(int i=0;i<la;i++)
  {
    int k=a[i]-'a',di=t[now].son[k];
    while(di>1&&t[di].flag!=-1)
    {
      ans+=t[di].flag;
      t[di].flag=-1;
      di=t[di].nt;
    }
    now=t[now].son[k];
  }
  return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
  cin>>a;
  ins(a);
}
cin>>a;
g();
cout<<walk(a);
return 0;
}

数据结构太恶心了www

2021/7/19 12:03
加载中...