- 浏览: 380185 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (229)
- java编程 (4)
- java实用程序 (2)
- 算法设计 (34)
- 数据库 (8)
- ACM模板 (12)
- 技术术语 (1)
- java_web (3)
- php (22)
- eclipse (3)
- linux (25)
- linux命令使用心得 (3)
- web服务器 (8)
- IT知识 (2)
- 前端技术 (17)
- 开源软件 (5)
- vim (3)
- linux多线程 (9)
- web开发经验 (3)
- lua (5)
- linux编程 (3)
- smarty (1)
- mysql (4)
- Hive (2)
- 数据挖掘 (9)
- python (2)
- 生活 (1)
- C++ (2)
- 计算机 (1)
- objective-c (11)
- css (2)
- 游戏 (1)
- Mac (1)
最新评论
-
lr544463316:
我的怎么不行呀.....
Mysql Access denied for user ''@'localhost' to database 的一种解决方法 -
babaoqi:
使用时需要注意group_concat函数返回值的最大长度=g ...
mysql中的group_concat函数 -
代码能力弱成渣:
可以帮我看下我的代码么?我自己写的sam,也有ac过题的,但是 ...
求两个字符串的最长公共连续子序列(SAM实现) -
atgoingguoat:
有1000个?不过还是收藏下。
jquery常用的插件1000收集(转载)
/* AC自动机,增设虚拟节点,求长度为n的字符串中包含至少k个给出的关键字的字符串的个数,结果模MOD。 增设虚拟节点的目的是为了方便状态转移。 dp转移实际上是在安全图上进行的! */ #include <cstdio> #include <cstring> #include <map> using namespace std; const int N= 55*20; //节点个数的最大值 const int S=4; //不同的字符 个数 const int MOD=20090717; const int LEN=1005; //n的最大值 struct node{ node *sons[S], *fail; int id; //id是节点的标号 bool flag; //标记该节点是否是安全的 }nodes[N], *root; int cnt; //cnt是树中节点的 个数 node *que[N]; int n, m, k; int dp[2][N]; map<char, int> mci; map<int, char> mic; char str[LEN]; void init(){ mci['A']=0; mic[0]='A'; mci['G']=1; mic[1]='G'; mci['C']=2; mic[2]='C'; mci['T']=3; mic[3]='T'; } void clear(){ cnt=0; root=NULL; } node* newNode(){ node* ans=&nodes[cnt]; memset(ans->sons, 0, S*sizeof(node*)); ans->fail=NULL; ans->id=cnt++; ans->flag=true; return ans; } int hash(char ch){ //字符的哈希函数,根据不同的需要而定 return mci[ch]; } //j表示当前关键字的标号 void insert(node*& root, char* str){ node* t=root; int i, k; for(i=0; str[i]; i++){ if(t->sons[k=hash(str[i])]==NULL){ t->sons[k] = newNode(); } t=t->sons[k]; } t->flag=false; } //在某些时候还需要吧root的S个儿子节点中为空赋值为root(所谓的虚拟节点,树中的 其他节点也可以 //添加类似的虚拟节点) void getFail(node*& root){ int l, r, i; node *t; l=r=0; root->fail=root; //这样可以保证每个节点的fail指针都是非空的 for(que[r++]=root; l!=r; ){ t=que[l++]; for(i=0; i<S; i++){ if(t->sons[i]){ que[r++]=t->sons[i]; if(t==root){ t->sons[i]->fail=t; }else{ t->sons[i]->fail=t->fail->sons[i]; } if(!t->sons[i]->fail->flag){ t->sons[i]->flag=false; } }else{ //增设虚拟节点 if(t==root) t->sons[i]=t; else t->sons[i]=t->fail->sons[i]; } } } } bool input(){ int n; scanf("%d", &n); if(n==0)return false; int i; char s[25]; clear(); root=newNode(); for(i=0; i<n; i++){ scanf("%s", s); insert(root, s); } return true; } int ca=0; void solve(){ getFail(root); int u, v, i, j, k, nxt, tmp; for(i=0; i<cnt; i++){ dp[0][i]=-1; } dp[0][0]=0; scanf("%s", str); for(u=0, i=0; str[i]; i++){ v=u^1; for(j=0; j<cnt; j++){ dp[v][j]=-1; } for(j=0; j<cnt; j++){ if(dp[u][j]==-1) continue; for(k=0; k<S; k++){ if(!nodes[nxt=nodes[j].sons[k]->id].flag) continue; tmp = dp[u][j]; if(str[i]!=mic[k]){ tmp++; } if(dp[v][nxt]==-1 || dp[v][nxt]>tmp){ dp[v][nxt]=tmp; } } } /* *这里dp[v][k]表示长度为字符串str的前i个字符组成的子串走到节点k需要改变的最少次数, *这个走到节点k可以这样来理解,该子串的后面部分等于节点k代表的字符串!例如子串为abbc, *节点k代表的字符串是bb,那么该子串走到节点k的时候就成了abbb了,所以就容易理解为什么 *会有下面这一句了,因为要把最后一个字符c变成b! *if(str[i]!=mic[k]){ tmp++; } */ u=v; } int ans=-1; for(j=0; j<cnt; j++){ if(!nodes[j].flag) continue; if(dp[u][j]!=-1 && (ans==-1 || ans>dp[u][j])){ ans=dp[u][j]; } } printf("Case %d: %d\n", ++ca, ans); } int main(){ //freopen("in.txt", "r", stdin); init(); while(input()) solve(); return 0; }
发表评论
-
升序数组中求一个key出现的次数
2013-01-09 23:08 1069算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需 ... -
判断单链表是否有环
2013-01-08 19:07 888算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次 ... -
hdu3684
2011-11-15 20:11 894/* 刚开始打了个记录上下左右四个点的,一直tle。 ... -
hdu3686
2011-11-14 20:43 1006/* 无向图边的双连通分量,在同一个连通分量里的边之间 ... -
poj3968
2011-11-14 04:45 1379source: http://poj.org/problem ... -
uva2819
2011-11-13 02:20 864source: http://livearchive.onli ... -
manacher算法
2011-11-11 00:06 2412const int LEN=110005; const ... -
hdu4118
2011-11-09 21:53 1163枚举每条边最多被经过的次数即可 #include ... -
hdu4115
2011-11-09 16:27 999source: http://acm.hdu.edu.cn/ ... -
uva(Transitive Closure)
2011-11-08 14:45 884source: http://livearchive.onli ... -
zoj3500
2011-11-07 17:41 927求两个球的体积交或者并 #include <cs ... -
zoj3545
2011-11-04 18:18 842/* AC自动机 相当暴力的 解法: mark[i ... -
zoj3190
2011-11-04 17:34 1256/* * AC自动机,先对资源串和病毒串构成的字符串 ... -
zoj3228
2011-11-04 16:12 929/* * AC自动机,每个节点 添加一个d表示节点代 ... -
hdu2825
2011-11-04 11:53 961/* AC自动机,增设虚拟节点,求长度为n的字符 ... -
hdu4095
2011-11-03 13:19 991/* 第一步,构建BST,用第一个数作为bst的 ... -
zoj3540
2011-11-02 21:33 895/* 其实就是把总共的 放置次数减去不能放置的那些就行 ... -
poj1741(树的分治,基于边的 分治)
2011-11-02 20:25 3328/* 树基于边的分治算法,计算树中距离小于等于k的点 ... -
hdu2939
2011-10-29 18:36 823source: http://acm.hdu.edu.cn/s ... -
hdu3982
2011-10-29 10:20 909//半平面交+多边形和圆的交的面积 #include ...
相关推荐
DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34868 Accepted: 13480 Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are ...
北大POJ1007-DNA Sorting 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj dna sorting 问题,研究的ac coderrrrrrr
简单的字符串操作和求逆序对数,是程设poj习题
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类