P2414 [NOI2011]阿狸的打字机
暴力跑AC自动机,询问离线,只有70分
好像还得建fail树,这又是什么高端操作==
#include<bits/stdc++.h> using namespace std; #define maxn 100004 struct Trie { int trie[maxn][26]; int tot,rt; int fail[maxn]; int val[maxn]; int ans[maxn]; vector<int>ed [maxn]; void init() { tot=-1; newNod(); } int newNod() { memset(trie[++tot],0,sizeof trie[0]); fail[tot]=val[tot]=0; return tot; } void insert(char *s,int k) { int cur=0; for(int i=0; s[i]; i++) { if(trie[cur][s[i]-'a']==0) { trie[cur][s[i]-'a']=newNod(); } cur=trie[cur][s[i]-'a']; } ++val[cur]; ed[cur].push_back(k); } void build() { queue<int> q; for(int i=0; i<26; i++) { if(trie[0][i]) { q.push(trie[0][i]); } } while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0; i<26; i++) { if(trie[u][i]) { fail[trie[u][i]]=trie[fail[u]][i]; q.push(trie[u][i]); } else trie[u][i]=trie[fail[u]][i]; ; } } } int query(char *s,int k) { for(int i=0;i<=k;i++)ans[i]=0; int cur=0,res=0; for(int i=0; s[i]; i++) { if(trie[cur][s[i]-'a']) { cur=trie[cur][s[i]-'a']; int tmp=cur; while(tmp&&val[tmp]>=0) { for(int i=0; i<ed[tmp].size(); i++) { ans[ed[tmp][i]]+=1; } //res+=val[tmp]; tmp=fail[tmp]; } } } return res; } } ac; int m; struct QAQ { int x,y; int i; int v; } Q[maxn]; bool cmp(QAQ a,QAQ b) { if(a.x==b.x)return a.y<b.y; return a.x<b.x; } bool cmp1(QAQ a,QAQ b) { return a.i<b.i; } char A[maxn]; char B[maxn]; char* T[maxn]; vector<char*>v; void work() { v.push_back(""); int j=0,k=1; for(int i=0; A[i]; i++) { if(A[i]=='P') { B[j]='\0'; // char t[maxn]; T[k]=new char[strlen(B)+1]; strcpy(T[k],B); ac.insert(T[k],k); v.push_back(T[k++]); } else if(A[i]=='B') { j--; } else { B[j]=A[i]; j++; } } /* for(int i=0;i<v.size();i++){ cout<<v[i]<<'\n'; }*/ ac.build(); } void ask() { int t=-1; int k=v.size(); for(int i=0; i<m; i++) { if(strlen(v[Q[i].x])<strlen(v[Q[i].y])){ Q[i].v=0; } else if(t!=Q[i].x) { //cout<<v[Q[i].x]<<'\n'; ac.query(v[Q[i].x],k); t=Q[i].x; Q[i].v=ac.ans[Q[i].y]; } else Q[i].v=ac.ans[Q[i].y]; } } int main() { scanf("%s",A); work(); scanf("%d",&m); for(int i=0; i<m; i++) { scanf("%d%d",&Q[i].y,&Q[i].x); Q[i].i=i; } sort(Q,Q+m,cmp); ask(); sort(Q,Q+m,cmp1); for(int i=0;i<m;i++){ cout<<Q[i].v<<'\n'; } }