次个字符串代表了相关操作后指定的可怜字符串。代表充分字符串从 aa位到 bb 位的子串的哈希值。

HDU   5687

度熊手上有一样据字典存储了大量的单词,有同等次等,他把有单词组成了一个深丰富好丰富的字符串。现在劳动来了,他记不清了原本的字符串都是呀,神奇之是外还记得原来那些字符串的哈希值。一个字符串的哈希值,由以下公式计算得到: 

Problem Description

H(s)=∏i≤len(s)i=1(Si−28) (mod 9973)
SiSi代表 S[i] 字符的 ASCII 码。 

度熊手上有同等本神奇的字典,你可当其里面做如下三个操作:
  1、insert : 往神奇字典中插入一个单词
  2、delete: 在神奇字典中剔除所有前缀等于让定字符串的单词
  3、search: 查询是否当神奇字典中出一个字符串的前缀等于给定的字符串

请帮忙度熊计算大字符串中随机一段落的哈希值是稍微。

Input

Input多组测试数据,每组测试数据第一执行是一个刚整数NN,代表摸底的次数,第二实践一个字符串,代表题目中的大字符串,接下NN行,每行包含两只刚整数aa和bb,代表摸底的开局位置以及罢位置。 

此间才发生同等组测试数据。第一实施输入一个正整数N(1≤N≤100000),代表度熊对于字典的操作次数,接下N行,每行包含两个字符串,中间受之所以空格隔开。第一只字符串代表了有关的操作(包括:
insert, delete 或者
search)。第二个字符串代表了系操作后指定的异常字符串,第二只字符串的长不会见越30。第二独字符串仅由小写字母组成。

1≤N≤1,0001≤N≤1,000 

Output

1≤len(string)≤100,0001≤len(string)≤100,000 

对于每一个search
操作,如果以度熊的字典中存在给定的字符串为前缀的单词,则输出Yes 否则输出
No。

1≤a,b≤len(string)1≤a,b≤len(string) 
Output对于各一个叩问,输出一个整数价,代表大字符串从 aa位至 bb 位的子串的哈希值。Sample
Input

Sample Input

2
ACMlove2015
1 11
8 10
1
testMessage
1 1

5

Sample
Output

insert hello

6891
9240
88
原题:HDU - 5685 
解题思路:线段树问题,第一次做不知道连乘的符号;

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 const int MAX = 1000000*10;
 7 int N;
 8 char a[MAX];
 9 int A[MAX];
10 
11 struct Seg
12 {
13     int veg;
14 }seg[MAX];
15 
16 void CJ(int root,int istrct,int iend,int A[])
17 {
18     if(istrct == iend)
19     {
20         seg[root].veg = A[iend];
21     }
22     else
23     {
24         int mid = (istrct+iend)/2;
25         CJ(root*2+1,istrct,mid,A);
26         CJ(root*2+2,mid+1,iend,A);
27         seg[root].veg = seg[root*2+1].veg*seg[root*2+2].veg%9973;
28     }
29 }
30 
31 int Cha(int root,int istrct,int iend ,int nstrct,int nend)
32 {
33     if(nstrct >iend||nend < istrct)
34         return 1;
35     if(nstrct <= istrct&&nend >=iend)
36     {
37         return seg[root].veg;
38     }
39 
40     int mid = (istrct + iend)/2;
41     return Cha(root*2+1,istrct,mid,nstrct,nend)*Cha(root*2+2,mid+1,iend,nstrct,nend)%9973;
42 }
43 
44 int main()
45 {
46     while(cin>>N)
47     {
48         scanf("%s",a);
49         int len = strlen(a);
50         for(int i =1;i <=len;i++)
51         {
52             int temp = a[i-1] - 28;
53             A[i] = temp;
54         }
55         CJ(0,1,len,A);
56         int x,y;
57         while(N--)
58         {
59             cin>>x>>y;
60             cout<<Cha(0,1,len,x,y)<<endl;
61         }
62 
63     }
64 
65     return 0;
66 }

insert hehe

search h

delete he

search hello

Sample Output

Yes

No

Source

2016″百度之星” – 资格赛(Astar
Round1)

Recommend

liuyiding   |   We have carefully selected several similar problems for
you:  5689 5688 5686 5685 5684 

 

思路:使用trie树,在每个节点受到投入num标记字符串的个数;

 

代码如下:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct node{
    int num;
    node *next[30];
    node(){
        memset(next,0,sizeof(next));
        num=0;  ///值得一学的好处理方法 简单实用 初始化节点的漂亮代码
    }
}Trie;
char dir[32],s[32];
void Insert(node *root,char *s){
    node *p=root;
    for(int i=0; s[i]; i++){
        int x=s[i]-'a';
        if(p->next[x]==NULL)
        p->next[x]=new node;
        p=p->next[x];
        p->num++;
    }
}
int Search(node *root,char *s)
{
    node *p=root;
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';
        if(p->next[x]==NULL)
        return 0;
        p=p->next[x];
    }
    return p->num;
}
void Delete(node *root,char *s,int cnt)
{
    node *p=root;
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';
        p=p->next[x];
        p->num-=cnt;  //删除节点的操作无非就是把当前前缀开头单词数减掉
    }
    for(int i=0;i<30;i++)
    p->next[i]=0;  //再把之后所有的孩子一律杀死(吼吼 好残忍)
}

int main()
{
    int n;
    scanf("%d",&n);
    Trie *root=new node;
    while(n--)
    {
        scanf("%s %s",dir,s);
        if(dir[0]=='i')
        {
            Insert(root,s);
        }
        else if(dir[0]=='s')
        {
            if(Search(root,s))
                printf("Yes\n");
            else
                printf("No\n");
        }
        else
        {
            int cnt=Search(root,s);
            if(cnt) Delete(root,s,cnt);
        }
    }
    return 0;
}

 

 

相关文章