没有合适的资源?快使用搜索试试~ 我知道了~
kuangbin的ACM模板
需积分: 19 34 下载量 181 浏览量
2017-09-17
18:08:18
上传
评论 1
收藏 197KB DOCX 举报
温馨提示
试读
64页
kuangbin的ACM模板kuangbin的ACM模板kuangbin的ACM模板kuangbin的ACM模板kuangbin的ACM模板kuangbin的ACM模板
资源推荐
资源详情
资源评论
上海大学 ACM 模板 by kuangbin
ACM 模
1 /
kuang
字符串处理....................................................................................................................... 2
数学................................................................................................................................. 17
数据结构......................................................................................................................... 42
图论................................................................................................................................. 75
计算几何....................................................................................................................... 133
上海大学 ACM 模板 by kuangbin
ACM 模
2 /
kuang
2、凸包...................................................................................................................... 138
3、平面最近点对(HDU 1007)...............................................................................139
4、旋转卡壳.............................................................................................................. 140
5、半平面交.............................................................................................................. 146
6、三点求圆心坐标(三角形外心).......................................................................149
7、求两圆相交的面积............................................................................................... 150
8、Pick 公式............................................................................................................... 150
动态规划............................................................................................................................ 150
1、最长上升子序列 O(nlogn).................................................................................... 150
搜索.................................................................................................................................... 151
1、Dancing Links........................................................................................................ 151
其他.................................................................................................................................... 156
1、高精度.................................................................................................................. 156
2、完全高精度.......................................................................................................... 158
3、strtok 和 sscanf 结合输入....................................................................................163
4、解决爆栈,手动加栈...........................................................................................163
5、STL......................................................................................................................... 163
6、输入输出外挂....................................................................................................... 165
7、莫队算法.............................................................................................................. 166
8、VIM 配置............................................................................................................... 172
字符串处理
1、KMP 算法
/*
* next[]的含义:x[i-next[i]...i-1]=x[0...next[i]-1]
* next[i]为满足 x[i-z...i-1]=x[0...z-1]的最大 z 值(就是 x 的自身匹配)
*/
void kmp_pre(char x[],int m,int next[])
{
int i,j;
j=next[0]=-1;
i=0;
while(i<m)
{
while(-1!=j && x[i]!=x[j])j=next[j];
next[++i]=++j;
}
}
/*
* kmpNext[]的意思:next'[i]=next[next[...[next[i]]]] (直到 next'[i]<0 或者
x[next'[i]]!=x[i])
* 这样的预处理可以快一些
*/
void preKMP(char x[],int m,int kmpNext[])
{
int i,j;
j=kmpNext[0]=-1;
i=0;
while(i<m)
{
{
ACM 模
3 /
kuang
上海大学 ACM 模板 by kuangbin
while(-1!=j && x[i]!=x[j])j=kmpNext[j];
if(x[++i]==x[++j])kmpNext[i]=kmpNext[j];
else kmpNext[i]=j;
}
}
/*
* 返回 x 在 y 中出现的次数,可以重叠
*/
int next[10010];
int KMP_Count(char x[],int m,char y[],int n)
{//x 是模式串,y 是主串
int i,j;
int ans=0;
//preKMP(x,m,next);
kmp_pre(x,m,next);
i=j=0;
while(i<n)
{
while(-1!=j && y[i]!=x[j])j=next[j];
i++;j++;
if(j>=m)
{
ans++;
j=next[j];
}
}
return ans;
}
经典题目:POJ 3167
/*
* POJ 3167 Cow Patterns
* 模式串可以浮动的模式匹配问题
* 给出模式串的相对大小,需要找出模式串匹配次数和位置
* 比如说模式串:1,4,4,2,3,1 而主串:5,6,2,10,10,7,3,2,9
* 那么 2,10,10,7,3,2 就是匹配的
*
* 统计比当前数小,和于当前数相等的,然后进行 kmp
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=100010;
const int MAXM=25010;
int a[MAXN];
int b[MAXN];
int n,m,s;
int as[MAXN][30];
int bs[MAXM][30];
void init()
{
for(int i=0;i<n;i++)
ACM 模
4 /
kuang
上海大学 ACM 模板 by kuangbin
if(i==0)
{
for(int j=1;j<=25;j++)as[i][j]=0;
}
else
{
for(int j=1;j<=25;j++)as[i][j]=as[i-1][j];
}
as[i][a[i]]++;
}
for(int i=0;i<m;i++)
{
if(i==0)
{
for(int j=1;j<=25;j++)bs[i][j]=0;
}
else
{
for(int j=1;j<=25;j++)bs[i][j]=bs[i-1][j];
}
bs[i][b[i]]++;
}
}
int next[MAXM];
void kmp_pre()
{
int i,j;
j=next[0]=-1;
i=0;
while(i<m)
{
int t11=0,t12=0,t21=0,t22=0;
for(int k=1;k<b[i];k++)
{
if(i-j>0)t11+=bs[i][k]-bs[i-j-1][k];
else t11+=bs[i][k];
}
if(i-j>0)t12=bs[i][b[i]]-bs[i-j-1][b[i]];
else t12=bs[i][b[i]];
for(int k=1;k<b[j];k++)
{
t21+=bs[j][k];
}
t22=bs[j][b[j]];
if(j==-1 || (t11==t21&&t12==t22))
{
next[++i]=++j;
}
else j=next[j];
}
}
vector<int>ans;
void kmp()
{
ans.clear();
int i,j;
kmp_pre();
上海大学 ACM 模板 by kuangbin
ACM 模
5 /
kuang
i=j=0;
while(i<n)
{
int t11=0,t12=0,t21=0,t22=0;
for(int k=1;k<a[i];k++)
{
if(i-j>0)t11+=as[i][k]-as[i-j-1][k];
else t11+=as[i][k];
}
if(i-j>0)t12=as[i][a[i]]-as[i-j-1][a[i]];
else t12=as[i][a[i]];
for(int k=1;k<b[j];k++)
{
t21+=bs[j][k];
}
t22=bs[j][b[j]];
if(j==-1 || (t11==t21&&t12==t22))
{
i++;j++;
if(j>=m)
{
ans.push_back(i-m+1);
j=next[j];
}
}
else j=next[j];
}
}
int main()
{
while(scanf("%d%d%d",&n,&m,&s)==3)
{
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<m;i++)
{
scanf("%d",&b[i]);
}
init();
kmp(); printf("%d\
n",ans.size()); for(int
i=0;i<ans.size();i++)
printf("%d\n",ans[i]);
}
return 0;
}
2、扩展 KMP
/*
* 扩展 KMP 算法
*/
//next[i]:x[i...m-1]与 x[0...m-1]的最长公共前缀
剩余63页未读,继续阅读
资源评论
genuinecai
- 粉丝: 3
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功