HDU 2222 키워드 검색 (AC 자동 템 플 릿)
이 문 제 는 대략 몇 개의 패턴 문자열, 한 개의 메 인 문자열 을 주 고 몇 개의 패턴 문자열 이 메 인 문자열 에 일치 하 는 지 물 어 보 는 것 이다.
AC 자동 동기 템 플 릿 문제 입 니 다. 최적화 할 수 있 는 부분 은 특정한 패턴 문자열 이 일치 하 는 것 입 니 다. 다음 에 여 기 를 지나 면 temp 지침 의 과정 을 뛰 어 넘 을 수 있 습 니 다.
코드 는 kuangbin 의 거대 한 블 로 그 를 참고 합 니 다. 너무 간결 합 니 다 (300 + ms):
1 #include
2 #include
3 #include
4 using namespace std;
5 int tn,ch[510000][26],cnt[510000],fail[510000];
6 void insert(char *s){
7 int x=0;
8 for(int i=0; s[i]; ++i){
9 int y=s[i]-'a';
10 if(ch[x][y]==0) ch[x][y]=++tn;
11 x=ch[x][y];
12 }
13 ++cnt[x];
14 }
15 void init(){
16 memset(fail,0,sizeof(fail));
17 queue<int> que;
18 for(int i=0; i<26; ++i){
19 if(ch[0][i]) que.push(ch[0][i]);
20 }
21 while(!que.empty()){
22 int x=que.front(); que.pop();
23 for(int i=0;i<26;++i){
24 if(ch[x][i]) que.push(ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i];
25 else ch[x][i]=ch[fail[x]][i];
26 }
27 }
28 }
29 int query(char *s){
30 int x=0,res=0;
31 for(int i=0; s[i]; ++i){
32 int tmp=x=ch[x][s[i]-'a'];
33 while(tmp){
34 if(cnt[tmp]>=0){
35 res+=cnt[tmp];
36 cnt[tmp]=-1;
37 }else break;
38 tmp=fail[tmp];
39 }
40 }
41 return res;
42 }
43 char S[1100000],T[55];
44 int main(){
45 int t,n;
46 scanf("%d",&t);
47 while(t--){
48 tn=0;
49 memset(ch,0,sizeof(ch));
50 memset(cnt,0,sizeof(cnt));
51 scanf("%d",&n);
52 while(n--){
53 scanf("%s",T);
54 insert(T);
55 }
56 init();
57 scanf("%s",S);
58 printf("%d
",query(S));
59 }
60 return 0;
61 }
또한 이전에 배 운 지침 버 전의 지침 버 전 은 더 빨리 달린다 (200 + ms).
1 #include
2 #include
3 #include
4 using namespace std;
5 typedef struct Node *pNode;
6 struct Node{
7 int cnt;
8 pNode fail,nxt[26];
9 Node(){
10 cnt=0; fail=NULL;
11 for(int i=0;i<26;++i) nxt[i]=NULL;
12 }
13 };
14 pNode root;
15 char S[1000100];
16 void insert(char *s){
17 pNode p=root;
18 for(int i=0;s[i];++i){
19 int index=s[i]-'a';
20 if(p->nxt[index]==NULL){
21 p->nxt[index]=new Node;
22 }
23 p=p->nxt[index];
24 }
25 ++p->cnt;
26 }
27 void init(){
28 queue que;
29 que.push(root);
30 while(que.size()){
31 pNode y=que.front(); que.pop();
32 for(int i=0;i<26;++i){
33 if(y->nxt[i]==NULL) continue;
34 if(y==root){
35 y->nxt[i]->fail=root;
36 que.push(y->nxt[i]);
37 continue;
38 }
39 pNode x=y->fail;
40 while(x&&x->nxt[i]==NULL) x=x->fail;
41 if(x==NULL) y->nxt[i]->fail=root;
42 else y->nxt[i]->fail=x->nxt[i];
43 que.push(y->nxt[i]);
44 }
45 }
46 }
47 int query(){
48 int res=0;
49 pNode x=root;
50 for(int i=0;S[i];++i){
51 int index=S[i]-'a';
52 while(x->nxt[index]==NULL&&x!=root) x=x->fail;
53 x=x->nxt[index];
54 if(x==NULL) x=root;
55 pNode y=x;
56 while(y!=root){
57 if(y->cnt>=0){
58 res+=y->cnt;
59 y->cnt=-1;
60 }else break;
61 y=y->fail;
62 }
63 }
64 return res;
65 }
66 int main(){
67 int t,n;
68 char s[55];
69 scanf("%d",&t);
70 while(t--){
71 root=new Node;
72 scanf("%d",&n);
73 for(int i=0;ii){
74 scanf("%s",s);
75 insert(s);
76 }
77 scanf("%s",S);
78 init();
79 printf("%d
",query());
80 }
81 return 0;
82 }
다음으로 전송:https://www.cnblogs.com/WABoss/p/5164457.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.