学习心得(code)

superlong@CoreCoder

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

公告

文字可能放在http://blog.csdn.net/superlong100,此处存放代码

常用链接

留言簿(4)

我参与的团队

搜索

  •  

最新随笔

最新评论

  • 1. re: Poj 1279
  • 对于一个凹多边形用叉积计算面积 后能根据结果的正负来判断给的点集的时针方向?
  • --bsshanghai
  • 2. re: Poj 3691
  • 你写的这个get_fail() 好像并是真正的get_fail,也是说fail指向的串并不是当前结点的子串。为什么要这样弄呢?
  • --acmer1183
  • 3. re: HDU2295[未登录]
  • 这个是IDA* 也就是迭代加深@ylfdrib
  • --superlong
  • 4. re: HDU2295
  • 评论内容较长,点击标题查看
  • --ylfdrib
  • 5. re: HOJ 11482
  • 呵呵..把代码发在这里很不错..以后我也试试...百度的编辑器太烂了....
  • --csuft1

阅读排行榜

评论排行榜

 

# include <stdio.h>
# include 
<string.h>

struct tree {
    tree 
*next[4], *fail;
    
int state, flag;
}
;

tree sta[
505];
int indexx;
int map[255];
int power[4], times[4];

tree 
*root, *p;

void newn() {
    sta[indexx].fail 
= NULL;
    sta[indexx].flag 
= 0;
    sta[indexx].state 
= indexx;
    
for(int i = 0; i < 4; i ++) sta[indexx].next[i] = 0;
}


void init() {
    indexx 
= 0;
    newn();
    root 
= &sta[indexx ++];
    map[
'A'= 0; map['C'= 1; map['G'= 2; map['T'= 3;
}


void insert(char ch[]) {
    
int id, i = 0;
    p 
= root;
    
while(ch[i]) {
        id 
= map[ch[i]];
        
if(!p->next[id]) {
            newn();
            p
->next[id] = &sta[indexx++];
        }

        p 
= p->next[id];
        i 
++;
    }

    p
->flag ++;
}


tree 
*que[10001];

void get_fail() {
    
int close = -1, open = 0, i;
    p 
= root; p->fail = root;
    que[
0= root;
    
while(close < open) {
        p 
= que[++close];
        
for(int i = 0; i < 4; i ++{
            
if(p->next[i] == 0{
                
if(p == root)    p->next[i] = root;
                
else            p->next[i] = p->fail->next[i];
            }
 else {
                
if(p == root)    p->next[i]->fail = root;
                
else {
                    p
->next[i]->fail = p->fail->next[i];
                    p
->next[i]->flag += p->fail->next[i]->flag;
                }

                que[
++open] = p->next[i];
            }

        }

    }

}



int f[5005][15005], num[4], tot;

void dfs(int s, int deep) {
    
if(deep == 4{
        
for(int i = 0; i < indexx; i ++)
            f[i][s] 
+= sta[i].flag;
        
for(int i = 0; i < indexx; i ++)
            
for(int j = 0; j < 4; j ++)
                
if( num[j] != times[j] && f[i][s + power[j]] < f[sta[i].next[j]->state][s] )
                    f[i][s 
+ power[j]] = f[sta[i].next[j]->state][s];
    }
 else {
        
for(int i = 0; i <= times[deep]; i ++{
            num[deep] 
= i;
            dfs(s, deep 
+ 1);
            s 
+= power[deep];
        }

    }

}


int dp() {
    
char str[40];
    
int L;
    scanf(
"%s", str);
    L 
= strlen(str);
    memset(times, 
0sizeof(times));
    
for(int i = 0; i < L; i ++{
        times[map[str[i]]] 
++;
    }

    power[
3= 1;
    
for(int i = 2; i >= 0; i --{
        power[i] 
= power[i+1* (times[i+1+ 1);
    }

    tot 
= power[0* (times[0+ 1);
    
for(int i = 0; i < indexx; i ++)
        
for(int j = 0; j < tot; j ++) f[i][j] = 0;
    dfs(
0 ,0);
    
int ans = f[0][tot-1];
    
return ans;
}


int n;
char dic[50][11];

int main() {
    
int t = 0;
    
while(scanf("%d"&n), n) {
        init();
        
for(int i = 0; i < n; i ++{
            scanf(
"%s", dic[i]);
            insert(dic[i]);
        }

        get_fail();
        
int ans = dp();
        printf(
"Case %d: %d\n",++t, ans);
    }

}

posted on 2010-03-22 11:14 superlong 阅读(296) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理