为什么这段代码过不了
查看原帖
为什么这段代码过不了
1122530
elpsconr楼主2024/5/16 02:31

一个点tle,一个点mle我要吐了,求解为什么

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+26;
int cnt[N][26],ne[N],n,st[N];
char s[N],idx;
void insert(char s[])
{
    int p=0,l=strlen(s);
    for(int i=0;i<l;++i)
    {
        int v=s[i]-'a';
        if(!cnt[p][v]) cnt[p][v]=++idx;
        p=cnt[p][v]; 
    }
    st[p]++;
}
void build()
{
  queue<int> q;
  for(int i=0;i<26;++i)
  {
    if(cnt[0][i]) q.push(cnt[0][i]),ne[cnt[0][i]]=0; 
  }
  while(!q.empty())
  {
    int x=q.front();q.pop();
    for(int i=0;i<26;++i)
    {
        int v=cnt[x][i];
        if(v) ne[v]=cnt[ne[x]][i],q.push(v);
        else cnt[x][i]=cnt[ne[x]][i];
    }
  }
}
int query(char s[])
{
    int ans=0,l=strlen(s),k=0;
    for(int i=0;i<l;++i)
    {
        k=cnt[k][s[i]-'a'];
        for(int j=k;j&&~st[j];j=ne[j])
        {
            ans+=st[j],st[j]=-1;
        }
    }
    return ans;
}
int main()
{
  cin.tie(0)->sync_with_stdio(0);
  cin>>n;
  for(int i=1;i<=n;++i)
  {
    cin>>s;insert(s);
  }
  build();
  cin>>s;
  int ans=query(s);
  cout<<ans<<endl;
  return 0;
}
2024/5/16 02:31
加载中...