c++ queue

2021-07-12 10:07

阅读：646

标签：tor include ace article i++ class front queue bitset

study from:

https://blog.csdn.net/cindywry/article/details/51919282

https://www.luogu.org/problemnew/show/P3808

  1 /*
  2 字符出现最多的次数
  3 */
  4 #include   5 #include   6 #include   7 #include   8 #include   9 #include string>
 10 #include set>
 11 #include  12 #include  13 #include  14 #include  15 #include  16 #include  17 #include  18 #include 
 19 #include  20 using namespace std;
 21 #define ll long long
 22 #define minv 1e-6
 23 #define inf 1e9
 24 #define pi 3.1415926536
 25 #define E  2.7182818284
 26 const ll mod=1e9+7;//998244353
 27 const int maxn=1e6+10;
 28 
 29 struct node
 30 {
 31     int c,hav,vis;
 32     node* pre;
 33     node* next[26];
 34     node* fail;
 35 }*tr,*be;
 36 queueq;
 37 
 38 char str[maxn];
 39 
 40 int main()
 41 {
 42     node *p,*d,*pos;
 43     int n,c,i,j,k,len,num=0,sum=0;
 44     tr=(node*) malloc (sizeof(node));
 45     tr->hav=0;
 46     tr->vis=0;
 47     for (i=0;i26;i++)
 48         tr->next[i]=NULL;
 49     scanf("%d",&n);
 50     while (n--)
 51     {
 52         scanf("%s",str);
 53         len=strlen(str);
 54         pos=tr;
 55         for (j=0;j)
 56         {
 57             c=str[j]-97;
 58             if (pos->next[c])
 59                 pos=pos->next[c];
 60             else
 61             {
 62                 p=(node*) malloc (sizeof(node));
 63                 for (k=0;k26;k++)
 64                     p->next[k]=NULL;
 65                 p->c=c;
 66                 p->hav=0;
 67                 p->vis=0;
 68                 pos->next[c]=p;
 69                 p->pre=pos;
 70                 pos=p;
 71             }
 72         }
 73         pos->hav++;
 74     }
 75     be=(node*) malloc (sizeof(node));
 76     for (i=0;i26;i++)
 77         be->next[i]=tr;///all!
 78     tr->pre=be;
 79 
 80     q.push(tr);
 81 
 82     while (!q.empty())
 83     {
 84         d=q.front();
 85         q.pop();
 86         if (d==tr)
 87             d->fail=be;
 88         else
 89         {
 90             pos=d->pre ->fail;
 91             c=d->c;
 92             while (pos->next[c] == NULL)
 93                 pos=pos->fail;
 94             d->fail=pos->next[c];
 95         }
 96 
 97         for (i=0;i26;i++)
 98             if (d->next[i])
 99                 q.push(d->next[i]);
100     }
101 
102     be->vis=1;
103     scanf("%s",str);
104     len=strlen(str);
105     pos=tr;
106     for (i=0;i)
107     {
108         c=str[i]-97;
109         if (pos->next[c])
110             pos=pos->next[c];
111         else
112         {
113             while (pos->next[c]==NULL)
114                 pos=pos->fail;
115             pos=pos->next[c];
116         }
117         d=pos;
118         while (d->vis==0)
119         {
120             d->vis=1;
121             sum+=d->hav;
122             d=d->fail;
123         }
124     }
125     coutsum;
126     return 0;
127 }
128 /*
129 2
130 ab
131 ac
132 abc
133 
134 2
135 ababc
136 abc
137 ababc
138 
139 3
140 ab
141 abc
142 abca
143 ababc
144 
145 6
146 ab
147 abc
148 abc
149 abc
150 abab
151 ababc
152 ababc
153 */

c++ queue

标签：tor include ace article i++ class front queue bitset

原文地址：https://www.cnblogs.com/cmyg/p/9547372.html

上一篇：SpaceVim 语言模块 elixir

下一篇：理解Python中的闭包

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：c++ queue
文章链接：http://soscw.com/essay/104116.html

亲，登录后才可以留言！

c++ queue

评论

热门文章

推荐文章

最新文章

置顶文章