没有合适的资源?快使用搜索试试~ 我知道了~
首页常用算法模板:字符串处理与素数筛选实例
常用算法模板:字符串处理与素数筛选实例
需积分: 0 0 下载量 115 浏览量
更新于2024-07-01
收藏 1.5MB PDF 举报
ACM模板1主要包含了常用的算法模板,涵盖了字符串处理、自动机和素数相关的知识点。在这个模板中,我们可以看到以下几个关键部分: 1. 字符串处理:这部分提供了几个操作字符串的函数或操作,例如RXR可能代表某种字符串搜索或替换操作,EJS和XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX可能是具体的实现细节。 2. 自动机:自动机在这里指的可能是正则表达式自动机或者后缀自动机。后缀数组和后缀自动机是处理字符串模式和查找模式出现位置的有效工具,如RX8和RX8XR表示后缀数组相关的内容,而RX8Xk可能涉及构建后缀自动机的具体步骤。 3. 后缀自动机:这个部分包括了后缀自动机的基本概念和操作,如基本函数(R8)和例题(RXeXk),用于解决字符串匹配问题和高效地搜索模式。 4. 素数:这是模板中的一个重要主题。k8标签下的内容涉及判断一个数是否为素数(kXR),筛选出小于等于指定数值的素数(kXRXk),以及区间内的素数筛选(k8 kXRXj 和 SPCke3N),这些都是基础的数论算法,常用于优化计算和数据结构设计。 5. 数学辅助:如数学函数(如扩展欧几里得算法,用于求解线性方程组的解和逆元,kd和kXj)在算法设计中也起到关键作用。 ACM模板1提供了一个全面的框架,将字符串处理和素数算法结合在一起,适合在竞赛编程或者算法研究中使用。理解并熟练掌握这些模板,能够大大提高编程效率和解决问题的能力。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/86288880/bg10.jpg)
38 else for(i = 0;i < tbc;i++)san[rn[i]] = i;
39 for(i = 0;i < tbc;i++) if(san[i] < tb)wb[ta++] = san[i] * 3;
40 if(n % 3 == 1)wb[ta++] = n − 1;
41 sort(r, wb, wa, ta, m);
42 for(i = 0;i < tbc;i++)wv[wb[i] = G(san[i])] = i;
43 for(i = 0, j = 0, p = 0;i < ta && j < tbc;p++)
44 sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j
++];
45 for(;i < ta;p++)sa[p] = wa[i++];
46 for(;j < tbc;p++)sa[p] = wb[j++];
47 }
48 //str 和 sa 也要三倍
49 void da(int str[],int sa[],int rank[],int height[],int n,int m){
50 for(int i = n;i < n*3;i++)
51 str[i] = 0;
52 dc3(str, sa, n+1, m);
53 int i,j,k = 0;
54 for(i = 0;i <= n;i++)rank[sa[i]] = i;
55 for(i = 0;i < n; i++){
56 if(k) k−−;
57 j = sa[rank[i]−1];
58 while(str[i+k] == str[j+k]) k++;
59 height[rank[i]] = k;
60 }
61 }
后缀自动机
基本函数
1 const int CHAR = 26;
2
const int
MAXN = 250010;
3 struct SAM_Node{
4 SAM_Node *fa,*next[CHAR];
5 int len;
6 long long cnt;
7 void clear(){
8 fa = 0;
9 memset(next,0,sizeof(next));
10 cnt = 0;
11 }
12 }pool[MAXN*2];
13 SAM_Node *root,*tail;
14 SAM_Node* newnode(int len){
15 SAM_Node* cur = tail++;
16 cur−>clear();
17 cur−>len = len;
18 return cur;
19 }
20 void SAM_init(){
21 tail = pool;
![](https://csdnimg.cn/release/download_crawler_static/86288880/bg11.jpg)
22 root = newnode(0);
23 }
24 SAM_Node* extend(SAM_Node* last,int x){
25 SAM_Node *p = last, *np = newnode(p−>len+1);
26 while(p && !p−>next[x])
27 p−>next[x] = np, p = p−>fa;
28 if(!p)np−>fa = root;
29 else {
30 SAM_Node* q = p−>next[x];
31 if(q−>len == p−>len+1)np−>fa = q;
32 else {
33 SAM_Node* nq = newnode(p−>len+1);
34 memcpy(nq−>next,q−>next,sizeof(q−>next));
35 nq−>fa = q−>fa;
36 q−>fa = np−>fa = nq;
37 while(p && p−>next[x] == q)
38 p−>next[x] = nq, p = p−>fa;
39 }
40 }
41 return np;
42 }
例题
给了一个 树,求 子树上的第 大的子串。
1 /*
2 * http://www.codechef.com/problems/TSUBSTR/
3 Input:
484
5 abcbbaca
612
723
814
945
10 4 6
11 4 7
12 1 8
13 abcdefghijklmnopqrstuvwxyz 5
14 abcdefghijklmnopqrstuvwxyz 1
15 bcadefghijklmnopqrstuvwxyz 5
16 abcdefghijklmnopqrstuvwxyz 100
17
18 Output:
19 12
20 aba
21
22 ba
23 −1
24 */
25 const int CHAR = 26;
![](https://csdnimg.cn/release/download_crawler_static/86288880/bg12.jpg)
26 const int MAXN = 250010;
27 struct SAM_Node{
28 SAM_Node *fa,*next[CHAR];
29 int len;
30 long long cnt;
31 void clear(){
32 fa = 0;
33 memset(next,0,sizeof(next));
34 cnt = 0;
35 }
36 }pool[MAXN*2];
37 SAM_Node *root,*tail;
38 SAM_Node* newnode(int len){
39 SAM_Node* cur = tail++;
40 cur−>clear();
41 cur−>len = len;
42 return cur;
43 }
44 void SAM_init(){
45 tail = pool;
46 root = newnode(0);
47 }
48 SAM_Node* extend(SAM_Node* last,int x){
49 SAM_Node *p = last, *np = newnode(p−>len+1);
50 while(p && !p−>next[x])
51 p−>next[x] = np, p = p−>fa;
52 if(!p)np−>fa = root;
53 else {
54 SAM_Node* q = p−>next[x];
55 if(q−>len == p−>len+1)np−>fa = q;
56 else {
57 SAM_Node* nq = newnode(p−>len+1);
58 memcpy(nq−>next,q−>next,sizeof(q−>next));
59 nq−>fa = q−>fa;
60 q−>fa = np−>fa = nq;
61 while(p && p−>next[x] == q)
62 p−>next[x] = nq, p = p−>fa;
63 }
64 }
65 return np;
66 }
67 char str[MAXN];
68 struct Edge
69 {
70 int to,next;
71 }edge[MAXN*2];
72 int head[MAXN],tot;
73 void addedge(int u,int v){
74 edge[tot].to = v;
75 edge[tot].next = head[u];
76 head[u] = tot++;
![](https://csdnimg.cn/release/download_crawler_static/86288880/bg13.jpg)
77 }
78
79 SAM_Node *end[MAXN];
80 int topcnt[MAXN];// 拓扑排序使用
81 SAM_Node *topsam[MAXN*2];
82 char s2[40];
83 int order[40];
84
85 int main()
86 {
87 int n,Q;
88 while(scanf("%d%d",&n,&Q) == 2){
89 scanf("%s",str+1);
90 memset(head,−1,sizeof(head));tot = 0;
91 int u,v;
92 for(int i = 1;i < n;i++){
93 scanf("%d%d",&u,&v);
94 addedge(u,v); addedge(v,u);
95 }
96 addedge(0,1);
97 SAM_init();
98 memset(end,0,sizeof(end));
99 end[0] = root;
100 queue<int>q;
101 q.push(0);
102 while(!q.empty()){
103 u = q.front();
104 q.pop();
105 for(int i = head[u];i != −1;i = edge[i].next){
106 v = edge[i].to;
107 if(end[v] != 0)continue;
108 end[v] = extend(end[u],str[v]−'a');
109 q.push(v);
110 }
111 }
112 memset(topcnt,0,sizeof(topcnt));
113 int num = tail − pool;
114 for(int i = 0;i < num;i++)topcnt[pool[i].len]++;
115 for(int i = 1;i <= n;i++)topcnt[i] += topcnt[i−1];
116 for(int i = 0;i < num;i++)topsam[−−topcnt[pool[i].len]] = &
pool[i];
117
118 for(int i = num−1;i >= 0;i−−){
119 SAM_Node *p = topsam[i];
120 p−>cnt = 1;
121 for(int i = 0;i < 26;i++)
122 if(p−>next[i])
123 p−>cnt += p−>next[i]−>cnt;
124 }
125 printf("%lld\n",root−>cnt);
126 long long k;
![](https://csdnimg.cn/release/download_crawler_static/86288880/bg14.jpg)
127 while(Q−−){
128 scanf("%s",s2);
129 for(int i = 0;i < 26;i++)order[i] = s2[i]−'a';
130 scanf("%lld",&k);
131 if(k > root−>cnt){
132 printf("−1\n");
133 continue;
134 }
135 SAM_Node *p = root;
136 //这里的第 k 个子串是从空串算起的
137 while((−−k) > 0 ){
138 for(int i = 0;i < 26;i++)
139 if(p−>next[order[i]]){
140 if(k <= p−>next[order[i]]−>cnt){
141 printf("%c",'a'+order[i]);
142 p=p−>next[order[i]];
143 break; //这个不要忘记
144 }
145 else k −=p−>next[order[i]]−>cnt;
146 }
147 }
148 printf("\n");
149 }
150 }
151 return 0;
152 }
给了 个字符串,求每个字符串有多少个至少出现在 个字符串中的子串
树,两遍 经典题。
1 /* http://codeforces.com/contest/204/problem/E
2 input
331
4 abc
5a
6 ab
7 output
8613
9 input
10 7 4
11 rubik
12 furik
13 abab
14 baba
15 aaabbbababa
16 abababababa
17 zero
18 output
19 1 0 9 9 21 30 0
20 */
21 const int CHAR = 26;
剩余265页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/1e5c2f31436c42edad420e1dd7651273_weixin_35831969.jpg!1)
SeaNico
- 粉丝: 23
- 资源: 321
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)