[AC 자동 복습] 노 이 2011 너구리 타자기
그리고 작년 에 노 이의 너구리 타자기 가 아직 쓰 여 있 지 않다 는 것 을 어색 하 게 알 게 되 었 습 니 다. 작년 여름 방학 에 AC 자동 동 기 를 몰라 서 움 직 이지 않 았 습 니 다. 나중에 계속 잊 어 버 렸 습 니 다.
쓸데없는 소리 하지 마.
모든 출력 단 어 를 AC 자동 동기 에 저장 합 니 다. 제목 이 특수 하기 때문에 일반적인 AC 자동 동기 보다 간단 합 니 다.
누 드 를 고려 하여 질문 (i, j) 에 대해 j 단어의 모든 점 을 매 거 합 니 다. 이 점 이 fail 포인터 로 i 의 끝 을 가리 킬 수 있다 면 ans + +;
이렇게 하면 당연히 AC 가 안 됩 니 다. 만약 에 fail 지침 을 반대로 한 다음 에 fail 트 리 를 만 들 면 j 의 점 에서 fail 지침 을 통 해 i 의 수량 으로 갈 수 있 습 니 다. fail tree 에 있 는 i 뿌리의 서브 트 리 와 같 습 니 다.
j 단어의 점 이 몇 개 있 습 니까?
이렇게 하면 우리 가 fail tree 에 있다 고 가정 한 후에 j 단어의 점 에 가중치 가 있다 면 우 리 는 dfs 서열 + 트 리 배열 / 선분 트 리 로 쉽게 통계 할 수 있다.그러면 dfs 라 는 trie 를 고려 할 수 있 습 니 다. dfs 과정 에서 fail tree 의 가중치 를 수정 하면 dfs 에서 j 단어 끝까지 쉽게 할 수 있 습 니 다. j 단어 에 있 는 점 만 가중치 가 있 습 니 다. 이렇게 오프라인 방법 으로 모든 질문 을 처리 할 수 있 습 니 다.
AC 자동 동 기 는 별로 틀 리 지 않 을 것 같 습 니 다. 한 번 지나 갔습니다.
# include <cstdlib>
# include <cstdio>
# include <cmath>
# include <cstring>
using namespace std;
const int maxn = 100000+5;
struct list
{
int top, linke[maxn*2+10], sum[maxn*2+10], next[maxn*2+10];
void link(int x, int y)
{
++top; next[top]= linke[x]; linke[x]=top; sum[top]=y;
}
}ans, edge;
int n, len;
int tot,end[maxn], fail[maxn], map[maxn][26], pre[maxn];
char s[maxn];
int l,r,que[maxn],st[maxn],have,ask[maxn], sol[maxn];
int head[maxn], tail[maxn], go[maxn], c[maxn];
void read()
{
int i,x,y;
scanf("%s
", s+1);
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d%d", &x, &y);
ans.link(y, x);
}
}
void build_AC()
{
int i,now=1; tot=1;len= strlen(s+1);
for (i = 1; i <= len; i++)
{
if (s[i]=='P') end[now]=++have, ask[have]=now;
else if (s[i]=='B') now=pre[now];
else now= map[now][s[i]-'a']==0? pre[++tot]=now,map[now][s[i]-'a']=tot: map[now][s[i]-'a'];
}
for (i = 0; i <= 25; i++)
if (map[1][i]) que[++r]=map[1][i], fail[que[r]]=1, edge.link(1, que[r]);
for (l=1;l<= r;l++)
for (i=0; i<=25; i++)
if (map[que[l]][i])
{
que[++r]=map[que[l]][i];
for (now=fail[que[l]]; now!=1&& map[now][i]==0;)now=fail[now];
fail[que[r]]= map[now][i]?map[now][i]:now;
edge.link(fail[que[r]], que[r]);
}
}
void pdfs(int now)
{
st[++st[0]]=now; head[now]=st[0]; go[now]=st[0];
for (int ke= edge.linke[now]; ke!=0; ke=edge.next[ke])
pdfs(edge.sum[ke]);
tail[now]=st[0];
}
void modify(int x, int d)
{
for (;x<=st[0];x+= x&(-x))
c[x]+= d;
}
int query(int x)
{
int ask=0;
for (;x>0;x-= x&(-x))
ask+= c[x];
return ask;
}
void work()
{
int i,now=1,ks;
for (i=1; i <= len; i++)
{
if (s[i]=='P');
else if (s[i]=='B') modify(go[now], -1),now=pre[now];
else now= map[now][s[i]-'a'], modify(go[now], 1);
if (ks=end[now])
{
for (int ke=ans.linke[ks]; ke!= 0; ke=ans.next[ke])
sol[ke]= query(tail[ask[ans.sum[ke]]])- query(head[ask[ans.sum[ke]]]-1);
end[now]=0;
};
}
}
int main()
{
//freopen("type.in", "r", stdin);
//freopen("type.out", "w", stdout);
read();
build_AC();
pdfs(1);
work();
for (int i = 1; i <= n; i++) printf("%d
", sol[i]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.