学习心得(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 <iostream>
#include 
<string.h>
using namespace std;

struct tree
{
    tree 
*next[26], *fail;
    
int flag, len, ;
};

tree 
*root, *p;
tree arr[
500001];
int  indexx;
char letter = 'a';

void newn()
{
    arr[indexx].fail 
= NULL;
    arr[indexx].flag 
= 0;
    arr[indexx].len 
= -1;
    
for(int i = 0; i < 26; i ++) arr[indexx].next[i] = 0;
}

void insert(char ch[], int w)
{
    p 
= root;
    
int tmp, i = 0;
    
while(ch[i])
    {
        tmp 
= ch[i] - letter;
        
if(p->next[tmp] == 0)
        {
            newn();
            p
->next[tmp] = &arr[indexx ++];
            p
->next[tmp]->len = p->len + 1;
        }
        p 
= p->next[tmp];
        i 
++;
    }
    
if(!p->flag)
        p
->flag = w;
}

tree 
*que[500005];

void get_fail()
{
    p
=root;
    p
->fail = root;
    
int open = 0, close = -1, i;
    que[
0= p;
    
while(close < open)
    {
        p 
= que[++ close];
        
for(i = 0; i < 26; 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];
                que[
++open] = p->next[i];
            }
        }
    }
}

int ans[2][100005];
int pos[100005];

void query(char ch[])
{
    p 
= root;
    tree 
*q;
    
int t, i = 0;
    
while(ch[i])
    {
        t 
= ch[i] - letter;
        p 
= p->next[t];
        q 
= p;
        
while(q != root && q->fail )
        {
            
if(q->flag)
            {
                ans[
0][q->flag] ++;
                
if(i - pos[q->flag] > q->len)
                {
                    ans[
1][q->flag] ++;
                    pos[q
->flag] = i;
                }
            }
            q 
= q->fail;
        }
        i 
++;
    }
}

int search(char ch[])
{
    p 
= root;
    
int tmp, i = 0;
    
while(ch[i])
    {
        tmp 
= ch[i] - letter;
        p 
= p->next[tmp];
        i 
++;
    }
    
return p->flag;
}

void init()
{
    indexx 
= 0;
    newn();
    root 
= &arr[indexx ++];
    memset(ans, 
0sizeof(ans));
    memset(pos, 
-1sizeof(pos));
}

char str[100005];
char dic[100005][7];
int  typed[100005];

int main()
{
    
int test = 0;
    
while(scanf("%s", str) != EOF)
    {
        
int n, i;
        init();
        scanf(
"%d"&n);
        
for(i = 1; i <= n; i ++)
        {
            scanf(
"%d %s"&typed[i], dic[i]);
            insert(dic[i], i);
        }
        get_fail();
        query(str);
        printf(
"Case %d\n",++test);
        
for(i = 1; i <= n; i ++)
        {
            
int id = search(dic[i]);
            printf(
"%d\n", ans[typed[i]][id]);
        }
        puts(
"");
    }
}

posted on 2009-09-08 12:17 superlong 阅读(439) 评论(0)  编辑 收藏 引用

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