【CUC集训】字典树+kmp+字符串hash题解

作者: 数字_ID | 来源:发表于2018-08-27 19:01 被阅读0次

制作：数字_ID
日期：2018年8月27日

A (HDU - 2087)

简单KMP，注意匹配成功之后j归0

#include <iostream>  
#include  <cstdio>  
#include <cstring>  
using namespace std;  
int nexta[1006];  
char t[1006],s[1006];  
void getnexta(char s[])  
{  
    memset(nexta,0,sizeof(nexta));  
    int n = strlen(s);  
    int k = -1,j = 0;  
    nexta[0] = -1;  
    while(j < n )  
    {  
  
        if(k == -1 || s[k] == s[j])  
        {  
            nexta[j + 1] = k + 1;  
            j ++;  
            k ++;  
        }  
        else  
        {  
            k = nexta[k];  
        }  
    }  
  
}  
int kmp(char s[],char t[])//t模式串，s母串.此种为返回首次匹配的位置，不能匹配则返回-1.  
{  
    getnexta(t);  
    int ans = 0;  
    int n = strlen(s),m = strlen(t);  
    int i = 0,j = 0;  
    while(i < n && j < m)  
    {  
        if(j == -1 || s[i] == t[j])  
        {  
            i ++;  
            j ++;  
        }  
        else  
        {  
            j = nexta[j];  
        }  
        if(j == m)//根据题目要求改变  
        {  
            ans ++;  
            j = 0;  
        }  
    }  
    return ans;  
}  
int main()  
{  
   // freopen("in.txt","r",stdin);  
    while(1)  
    {  
        scanf("%s",s);  
        if(strcmp(s,"#") == 0)  
            break;  
        scanf("%s",t);  
        printf("%d\n",kmp(s,t));  
    }  
    return 0;  
}

B(HDU - 1711)

kmp入门模板题

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define clrf(x) memset(x,-1,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Sd(x) scanf("%I64d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fucl:"<<__LINE__<<endl;
# define gcd(a,b) __gcd((a),(b))
# define maxn 720
using namespace std;

int n,m;
int T;

int s[1000100];
int p[10100];
int nexta[10100];

void getnxt(int P[])
{
    clr0(nexta);
    nexta[0] = -1;
    int i = -1,j = 0;
    W(j<m){
        if(i==-1||P[i]==P[j]){
            nexta[j+1] = i+1;
            i++;j++;
        }else {
            i = nexta[i];
        }
    }
}

int kmp(int s[],int t[])//t为模式串，s为原串
{
    getnxt(t);
    int res = -1;
    int i = 0,j =0 ;
    W(i<n&&j<m){
        if(j==-1||s[i] == t[j]){
            i++;j++;
        }else{
            j = nexta[j];
        }
    }
    if(j == m){
        res = i-j;//根据题目要求改变
    }
    return res;
}
int main()
{
    fuckio
    Sc(T);
    W(T--){
        scanf("%d%d",&n,&m);
        rep(i,n)Sc(s[i]);
        rep(i,m)Sc(p[i]);
        int res = kmp(s,p);
        if(res!=-1)res++;
        printf("%d\n",res);
    }
}

C（HDU - 1686）

kmp统计子串格式
可重叠
注意匹配成功之后j=nexta[j]

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define clrf(x) memset(x,-1,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Sd(x) scanf("%I64d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fucl:"<<__LINE__<<endl;
# define gcd(a,b) __gcd((a),(b))
# define maxn 10020
using namespace std;

int nexta[maxn];
void getnxt(string s)
{
    clr0(nexta);
    int m = s.length();
    nexta[0] = -1;
    int i = -1,j = 0;
    W(j<m){
        if(i==-1||s[i]==s[j]){
            nexta[j+1] = i+1;
            i++;j++;
        }else {
            i = nexta[i];
        }
    }
}

int kmp(string s,string t)//t为模式串，s为原串
{
    getnxt(t);
    int res = 0;
    int i = 0,j =0 ;
    int n = s.length();
    int m = t.length();
    W(i<n){
        if(j==-1||s[i] == t[j]){
            i++;j++;
        }else{
            j = nexta[j];
        }
        if(j == m){
            res ++;
            j = nexta[j];
        }
    }
    return res;
}
int main()
{
    fuckio
    string s;
    string t;
    int T;
    cin>>T;
    W(T--){
       cin>>t>>s;
       cout<<kmp(s,t)<<endl;
    }
}

D(HDU - 3746)

next数组的一共经典应用，统计字符串的循环节
希望大家这道题都能搞明白

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define clrf(x) memset(x,-1,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Sd(x) scanf("%I64d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fucl:"<<__LINE__<<endl;
# define gcd(a,b) __gcd((a),(b))
# define maxn 100020
using namespace std;

int nexta[maxn];
void getnxt(string s)
{
    clr0(nexta);
    int m = s.length();
    nexta[0] = -1;
    int i = -1,j = 0;
    W(j<m){
        if(i==-1||s[i]==s[j]){
            nexta[j+1] = i+1;
            i++;j++;
        }else {
            i = nexta[i];
        }
    }
}


int main()
{
    fuckio
    string s;
    int T;
    Sc(T);
    W(T--){
        cin>>s;
        getnxt(s);
        int len = s.length();
        int min_repeat=len-nexta[len];
        if(len!=min_repeat&&len%min_repeat==0)  
            printf("0\n");
        else
            printf("%d\n",min_repeat-len%min_repeat); 

    }
}

E(HDU - 1251)

字典树板子题，flag维护前缀出现的次数

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define clrf(x) memset(x,-1,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Sd(x) scanf("%I64d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define gcd(a,b) __gcd((a),(b))
# define maxn 100020

using namespace std;

const int ALTN = 30;
struct Node
{
    int flag;
    Node *nxt[ALTN];
    Node(){
        flag = 0;
        rep(i,ALTN)nxt[i] = NULL;
    }
};
Node *root;
void init()
{
    root = new Node();
}

void ins(char *s)
{
    int len = strlen(s);
    Node *now = root;
    rep(i,len){
        now->flag++;
        int to = s[i]-'a';
        if(now->nxt[to] == NULL)now->nxt[to] = new Node();
        now = now->nxt[to];
    }
    now->flag++;
}

int fid(char *s)
{
    int len = strlen(s);
    Node *now = root;
    rep(i,len){
        int to = s[i]-'a';
        if(now->nxt[to] == NULL)return 0;
        now = now->nxt[to];
    }
    return now->flag;
}


int main()
{
    fuckio
    char s[11];
    init();
    W(cin.getline(s,12)){
        if(strlen(s) == 0||s[0] == ' ')break;
        ins(s);
    }
    W(scanf("%s",s)!=EOF){
        printf("%d\n",fid(s));
    }
}

F(HihoCoder - 1366)

本来想让大家试着用字典树做，但时限给了10s，自然也就能用stl直接做
正序查找，倒叙插入

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define clrf(x) memset(x,-1,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Sd(x) scanf("%I64d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define gcd(a,b) __gcd((a),(b))
# define maxn 100020

using namespace std;

const int ALTN = 30;
struct Node
{
    int flag;
    Node *nxt[ALTN];
    Node(){
        flag = 0;
        rep(i,ALTN)nxt[i] = NULL;
    }
};
Node *root;
void init()
{
    root = new Node();
}

void ins(char *s)
{
    int len = strlen(s);
    Node *now = root;
    repd(i,len-1,0){
        int to = s[i]-'a';
        if(now->nxt[to] == NULL)now->nxt[to] = new Node();
        now = now->nxt[to];
    }
    now->flag++;
}

int fid(char *s)
{
    int len = strlen(s);
    Node *now = root;
    rep(i,len){
        int to = s[i]-'a';
        if(now->nxt[to] == NULL)return 0;
        now = now->nxt[to];
    }
    return now->flag;
}


int main()
{
    fuckio
    int n;Sc(n);
    int ans = 0;
    char s[30];
    init();
    W(n--){
        scanf("%s",s);
        ans += fid(s);
        ins(s);
        clr0(s);
    }
    printf("%d\n",ans);
}

G(UVA - 12338)

提议是询问两个字串的最长前缀匹配
符串hash+二分，hash的一个经典应用

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define clrf(x) memset(x,-1,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Sd(x) scanf("%I64d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define gcd(a,b) __gcd((a),(b))
# define maxn 100020

using namespace std;

typedef unsigned long long ull;

vector<ull>hashcode[maxn];
char str[maxn];
int strhash[maxn];

void gethash(int pos)
{
    int len = strlen(str);
    strhash[pos] = len;
    hashcode[pos].clear();
    hashcode[pos].push_back(0);
    repf(i,1,len)hashcode[pos].push_back(hashcode[pos][i-1]*233+str[i-1]);
}


int main()
{
    fuckio
    int T,N,Q,a,b,l,r,mid;
    Sc(T);
    repf(tt,1,T){
        printf("Case %d:\n",tt);
        Sc(N);
        repf(i,1,N){
            scanf("%s",str);
            gethash(i);
        }
        Sc(Q);
        W(Q--){
            scanf("%d%d",&a,&b);
            int len = min(strhash[a],strhash[b]);
            l = 0;r = len;
            W(l<r){
                mid = (l+r+1)/2;
                //fuck
                if(hashcode[a][mid] == hashcode[b][mid])l = mid;
                else r = mid-1;
            }
            printf("%d\n",l);
        }
    }
}

H(HDU - 4300)

给一个代换表，给一个混合明密文，密文完整明文缺失，问要补充的最小字符数
两个hash，假设全部是密文，翻译过来之后计算hash，已经翻译之前计算hash。从len/2枚举密文长度，翻译后的密文前缀和翻译前的明文后缀
扩展kmp也可做

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 100020


using namespace std;



typedef unsigned long long ull;
const ull base = 233;

ull hash1[maxn],hash2[maxn],p[maxn];
char s[maxn],t[30];
int cov[30];
void init(){
    p[0] = 1;
    for(int i = 1;i<maxn;i++)p[i] = p[i-1]*base;
}

ull gethash(int l,int r,ull h[])
{
    return h[r]-h[l-1]*p[r-l+1];
}




int main()
{
    fuckio
    init();
    int T;Sc(T);
    W(T--){
        clr0(cov);
        clr0(t);
        clr0(s);
        scanf("%s%s",t,s+1);
        rep(i,26){
            cov[t[i]-'a'] = i;
        }
        int len = strlen(s+1);
        hash1[0] = 0;
        hash2[0] = 0;
        repf(i,1,len){
            hash1[i] = hash1[i-1]*base+(cov[s[i]-'a']);
            hash2[i] = hash2[i-1]*base+(s[i]-'a');
        }
        int ans = len;
        repf(i,len,len*2){
            if(i&1)continue;
            int tmp = i/2;
            int cc = len-tmp;
            ull s1 = gethash(1,cc,hash1);
            ull s2 = gethash(tmp+1,len,hash2);
            //cout<<s1<<s2<<endl;
            if(s1 == s2){
                ans = tmp;
                //fuck
                break;
            }
        }
        repf(i,1,ans)printf("%c",s[i]);
        repf(i,1,ans)printf("%c",cov[s[i]-'a']+'a');
        printf("\n");
    }
return 0;
}

J(HDU - 4825)

从已知集合中选一个数是的询问中的数与选的这个数的异或值最大
01字典树，从高位到低位建树，贪心

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 200020

using namespace std;

struct Node{
    int flag;
    Node *nxt[2];
    Node(){
        rep(i,2)nxt[i] = NULL;
        flag = 0;
    }
};
Node *root;
void init()
{
    root = new Node();
}
void ins(int s)
{
    Node *now = root;
    int len = 32;
    repd(i,len-1,0){
        int to = (s>>i)&1;
        //cout<<to<<" ";
        if(now->nxt[to] == NULL)now->nxt[to] = new Node();
        now = now->nxt[to];
    }
    now->flag = s;
}

int fid(int s)
{
    Node *now = root;
    int len = 32;
    
    repd(i,len-1,0){
        int to =  (s>>i)&1;
        
        if(now->nxt[to^1] != NULL){
            //cout<<(to+1)%2<<" ";
            now = now->nxt[to^1];
        }else {
            //cout<<to<<" ";
            now = now->nxt[to];
        }
    }
    return now->flag;
}


int main()
{
    fuckio
    int T;Sc(T);
    int n,m;
    repf(tt,1,T){
        printf("Case #%d:\n",tt);
        init();
        Sc(n);Sc(m);
        rep(i,n){
            int a;Sc(a);
            //cout<<a<<": ";
            ins(a);
            //cout<<endl;
        }
        rep(i,m){
            int a;Sc(a);
            
            //cout<<endl;
            cout<<fid(a)<<endl;
            //printf("%d\n",fid(a));
        }
    }

}

【CUC集训】字典树+kmp+字符串hash题解

A (HDU - 2087)

B(HDU - 1711)

C（HDU - 1686）

D(HDU - 3746)

E(HDU - 1251)

F(HihoCoder - 1366)

G(UVA - 12338)

H(HDU - 4300)

J(HDU - 4825)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读