洛谷的板子
题目1
标程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 #include <iostream> #include <queue> #define maxn 1000001 using namespace std;bool b[maxn];string word,s; int ans=0 ;typedef struct A { A *fail; A *next[26 ]; int word; int num; void a () { for (int i=0 ;i<26 ;i++){ next[i]=NULL ; } fail=NULL ; word=0 ; num=0 ; } }node; node *root; void insert_word (int j) { int len=word.length (); node *p=root; for (int i=0 ;i<len;i++){ int k=word[i]-'a' ; if (p->next[k]==NULL ){ node *temp; temp=new node; temp->a (); p->next[k]=temp; } p=p->next[k]; } p->word=j; p->num++; } void fail () { queue<node *>q; q.push (root); while (!q.empty ()){ node *p=q.front (); q.pop (); for (int i=0 ;i<26 ;i++){ if (p->next[i]!=NULL ){ node *t=p->next[i]; if (p==root){ t->fail=root; } else { node *fafail=p->fail; while (fafail!=NULL ){ if (fafail->next[i]!=NULL ){ t->fail=fafail->next[i]; break ; } fafail=fafail->fail; } if (fafail==NULL )t->fail=root; } q.push (t); } } } } void query () { int len=s.length (); node *p=root; for (int i=0 ;i<len;i++){ int k=s[i]-'a' ; while (p!=root&&p->next[k]==NULL ) p=p->fail; p=p->next[k]; if (p==NULL ) p=root; node *temp=p; if (temp->word&&!b[temp->word]){ b[temp->word]=1 ; ans+=temp->num; } } } int main () { root=new node; root->a (); int n; cin>>n; for (int i=1 ;i<=n;i++){ cin>>word; insert_word (i); } fail (); while (cin>>s){ ans=0 ; query (); cout<<ans<<endl; } }
题目2
标程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 #include <iostream> #include <string.h> #include <stdio.h> #include <queue> #include <map> #include <algorithm> using namespace std;typedef struct A { int word; A* fail; A* next[26 ]; void aaa () { word=0 ; fail=NULL ; for (int i=0 ;i<26 ;i++) next[i]=NULL ; } }node; node *root; queue<node*>q; map<string,int >tmap; string word[200 ]; char t[1000010 ];int num[200 ];void insert (int x) { node *p=root; int len=word[x].length (); for (int i=0 ;i<len;i++){ int k=word[x][i]-'a' ; if (p->next[k]==NULL ){ node *new_node=new node; new_node->aaa (); p->next[k]=new_node; } p=p->next[k]; } p->word=x; } void build_fail () { q.push (root); while (!q.empty ()){ node *p=q.front (); q.pop (); for (int i=0 ;i<26 ;i++){ if (p->next[i]!=NULL ){ node *k=p->next[i]; q.push (k); if (p==root){ k->fail=root; } else { node *fafail=p->fail; while (fafail!=NULL ){ if (fafail->next[i]!=NULL ){ k->fail=fafail->next[i]; break ; } fafail=fafail->fail; } if (fafail==NULL )k->fail=root; } } } } } void query () { int len=strlen (t); node *p=root; for (int i=0 ;i<len;i++){ int k=t[i]-'a' ; while (p->next[k]==NULL &&p!=root)p=p->fail; p=p->next[k]; if (p==NULL )p=root; else { node *temp=p; while (temp!=root){ if (temp->word){ num[temp->word]++; } temp=temp->fail; } } } } int cmp1 (int a,int b) { return a>b; } int cmp (string a,string b) { if (num[tmap[a]]==num[tmap[b]])return tmap[a]<tmap[b]; return num[tmap[a]]>num[tmap[b]]; } int main () { int n; while (scanf ("%d" ,&n)&&n){ memset (num,0 ,sizeof (num)); tmap.clear (); root=new node; root->aaa (); for (int i=1 ;i<=n;i++){ cin>>word[i]; tmap[word[i]]=i; insert (i); } build_fail (); scanf ("%s" ,t); query (); sort (word+1 ,word+1 +n,cmp); sort (num+1 ,num+1 +n,cmp1); int maxnum=num[1 ]; cout<<maxnum<<endl; for (int i=1 ;i<=n;i++){ if (num[i]==maxnum){ cout<<word[i]<<endl; } } } return 0 ; }
题目3
标程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 #include <iostream> #include <string.h> #include <stdio.h> #include <queue> #include <map> #include <algorithm> #include <cstdlib> using namespace std;const int maxn = 2e6 + 5 ;struct node { int word;int deg,val; node *fail , *next[26 ]; node () { word = deg = val = 0 ;fail = NULL ; for (int i = 0 ;i < 26 ;i++) next[i] = NULL ; } }*ext=(node*)malloc (sizeof (node)*maxn),*root; queue<node*> Q; char t[maxn], word[maxn];int num[maxn],ans[maxn];inline node* Ot () {return *ext=node (),ext++;}void insert (int x) { node* p = root; int len = strlen (word); for (int i = 0 ;i < len;i++) { int k = word[i] - 'a' ; if (p->next[k] == NULL ) { p->next[k] = Ot (); } p = p->next[k]; } if (!p->word) { p->word = x; } num[x] = p->word; } void build_fail () { for (int i=0 ;i<26 ;i++) if (root->next[i]) root->next[i]->fail=root,Q.push (root->next[i]); else root->next[i]=root; while (!Q.empty ()) { node* p = Q.front ();Q.pop (); for (int i = 0 ;i < 26 ;i++) { if (p->next[i]) { p->next[i]->fail = p->fail->next[i],p->fail->next[i]->deg++; if (p->next[i]!=root) Q.push (p->next[i]); } else p->next[i] = p->fail->next[i]; } } } void query () { int len = strlen (t); node* p = root; for (int i = 0 ;i < len;i++) { int k = t[i] - 'a' ; p=p->next[k];p->val++; } } void topo () { for (node *i=root;i<ext;i++) if (!i->deg) Q.push (i); while (!Q.empty ()){ node *p=Q.front ();Q.pop ();ans[p->word]=p->val; if (p!=root){ p->fail->val += p->val; if (--p->fail->deg==0 ) Q.push (p->fail); } } } int main () { int n;scanf ("%d" , &n);root=Ot (); for (int i = 1 ;i <= n;i++) { scanf ("%s" , word); insert (i); } build_fail (); scanf ("%s" , t); query ();topo (); for (int i = 1 ;i <= n;i++) { cout<<ans[num[i]]<<endl; } return 0 ; }