對酒當歌,人生幾何? 譬如朝露,去日苦多

2017年11月

我参考的这个教程,特别稳,但是你要下载对安装包

https://tieba.baidu.com/p/4584670848?red_tag=1899904221&traceid=

1.百度一下“字典树 博客”,第一页的那个能看懂看那个,主要是思想+代码

2.入门题hdu1671

注意释放内存

代码

#include<stdio.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct tree
{
    tree *next[10];
    int f;
    int v;
};
char s[1005];
int flag;
tree *root;
void creat(char *str)
{
    int len=strlen(str);
    tree *p=root,*q;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'0';
        if(p->next[id]==NULL)
        {
            q=new tree;
            for(int i=0;i<=9;i++)
                q->next[i]=NULL;
            q->f=0;
            q->v=0;
            p->f=1;
            p->next[id]=q;
            p=q;
        }
        else
        {
            p=p->next[id];
            if(p->v==-1)
                flag=1;
        }
    }
    p->v=-1;
    if(p->f)
    {
        flag=1;
    }
}
void deal(tree *T)
{
    for(int i=0;i<=9;i++)
        if(T->next[i]!=NULL)
        deal(T->next[i]);
    delete T;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        root=new tree;
        for(int i=0;i<=9;i++)
        {
            root->next[i]=NULL;
        }
        root->f=0;
        root->v=0;
        memset(s,0,sizeof(s));
        int n;
        scanf("%d",&n);
        getchar();
        flag=0;
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            creat(s);
        }
        if(flag)
            printf("NO\n");
        else
            printf("YES\n");
            deal(root);
    }
    return 0;
}

 

1.入门视频https://www.bilibili.com/video/av7230433/

2.七种题型

(1):给两个字符串s1,s2,求s2是否是s1的子串,并求s2在s1中出现的次数(感觉用kmp比较好)。

(2):给出n个单词串,和一个文章串,求每个单词串是否是文章串的子串,并求出每个单词在文章中出现的次数。

(3):给两个字符串s1,s2,求它们的最长公共字串的长度。

(4):给一个字符串s,求s的最长回文字串。(manacher)

(5):给一个字符串s,求s的每个后缀与s的最长公共前缀(LCP)

(6):给一个字符串s,求s的最小表示法。

(7):给一个字符串s,求s的最长连续重复字串。