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

  • 制作：数字_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));
        }
    }

}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,099评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,828评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,540评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,848评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,971评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,132评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,193评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,934评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,376评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,687评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,846评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,537评论 4赞 335
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,175评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,887评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,134评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,674评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,741评论 2赞 351

推荐阅读更多精彩内容

  • KMP 专题整理
    KMP 学习记录 kuangbin专题十六——KMP KMP 学习总结 朴素 KMP 算法 拓展 KMP 算法（E...
    染微言阅读 558评论 0赞 3
  • KMP字符串搜索算法一
    字符串匹配KMP算法详解 1. 引言 以前看过很多次KMP算法，一直觉得很有用，但都没有搞明白，一方面是网上很少有...
    张晨辉Allen阅读 2,396评论 0赞 3
  • KMP_字符串匹配
    不错的博客求next数组: 注意:求next数组得到的最长公共前缀后缀是可以重叠的:比如:ababa,next[5...
    Gitfan阅读 845评论 0赞 0
  • 数据结构与算法--KMP算法查找子字符串
    数据结构与算法--KMP算法查找子字符串 部分内容和图片来自这三篇文章: 这篇文章、这篇文章、还有这篇他们写得非常...
    sunhaiyu阅读 1,731评论 1赞 21
  • KMP字符串匹配算法
    为什么要写KMP字符串匹配算法呢？因为近段时间在补数据结构和算法，然后重拾大学的《大话数据结构》，记录一下学习的进...
    一剑孤城阅读 4,348评论 0赞 8