模板整理

本文主要是介绍模板整理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

KMP模板：

KMP模板1：简单的字符串匹配

//KMP模板1，简单的字符串匹配

void GetNextVal(int* p) //得next数组；next[i]是下标为i的字符之前后缀和前缀相同的最长长度
{
    next[0]=-1;
    int k=-1,j=0;
    while(j<m-1)
    {
        if(k==-1||p[j]==p[k])
        {
            if(p[++j]==p[++k])  //当两个字符相等时要跳过（优化）
                next[j]=next[k];
            else
                next[j]=k;
        }
　　　　　　
        else
        {
            k=next[k];
        }
    }
}
int KmpSearch(int* s,int* p) //在主串中查找子串出现的位置
{
    int i=0,j=0; //i是主串的位置，j是模式串的位置
    while(i<n&&j<m)
    {
        if(j==-1||s[i]==p[j]) // j为-1，主串后移一位；当两个字符相同，就比较下一个
        {
            ++i;
            ++j;
        }
        else
        {
            j=next[j]; //只移动模式串，回到指定位置
        }
    }
    if(j==m)
        return i-j; //如果找到，返回在主串中第一个字符出现的下标，否则为-1

　　else  return -1; 
}

KMP模板2：求模式串在待匹配串中的出现次数（不重复）

//KMP模板2，求模式串在待匹配串中的出现次数（不重复）
void GetNextVal(char* p)
{
    next[0]=-1;
    int k=-1,j=0;
    while(j<m-1)//m为模式串长度
    {
        if(k==-1||p[j]==p[k])
        {
            if(p[++j]==p[++k])
                next[j]=next[k];
            else
                next[j]=k;
        }
        else
        {
            k=next[k];
        }
    }
}
int KmpSearch(char* s,char* p)
{
    int i=0,j=0,cnt=0;
    while(i<n)//n为主串长度
    {
        if(j==-1||s[i]==p[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j=next[j];
        }
        if(j==m)//m为模式串长度
        {
            cnt++;
            j=0;//找到之后模式串回到最开头位置
        }
    }
    return cnt;//返回出现次数
}

KMP模板3：求模式串在待匹配串中的出现次数（可重复）

//KMP模板3，求模式串在待匹配串中的出现次数（可重复）
void GetNextVal(char* p)
{
    next[0]=-1;
    int k=-1,j=0;
    while(j<m) //m为模式串长度
    {
        if(k==-1||p[j]==p[k]) //这里不要优化
        {
            next[++j]=++k;
        }
        else
        {
            k=next[k];
        }
    }
}
int KmpSearch(char* s,char* p)
{
    int i=0,j=0,cnt=0;
    while(i<n)//n为主串长度
    {
        if(j==-1||s[i]==p[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j=next[j];
        }
        if(j==m)//m为模式串长度
        {
            cnt++;
            j=next[j];//找到之后模式串回到指定位置
        }
    }
    return cnt;//返回出现次数
}

字符串循环节长度为：len - next[len] ;（len为字符串长度）//跑一个next数组即可

字典树模板：插入和查找

//字典树模板（插入和查找）
void insert()//插入单词s
{
    len=strlen(s);//单词s的长度
    root=0;//根节点编号为0
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';//第二种编号
        if(!trie[root][id])//如果之前没有从root到id的前缀 
                    trie[root][id]=++tot;//插入，tot即为第一种编号
        root=trie[root][id];//顺着字典树往下走
    }
}

bool find() //查找单词s
{
    len=strlen(s);
    root=0;//从根结点开始找
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';//
        if(trie[root][x]==0)   return false;//以root为头结点的x字母不存在，返回0 
        root=trie[root][x];//为查询下个字母做准备，往下走 
    }
    return true;//找到了
}

字典树完整模板1：查询前缀（或整个单词）是否出现

//字典树完整模板1，查询是否出现（前缀或整个单词）
/*
  trie tree的储存方式：将字母储存在边上，边的节点连接与它相连的字母 
  trie[rt][x]=tot:rt是上个节点编号，x是字母，tot是下个节点编号 
*/ 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 2000010
using namespace std;
int tot=1,n;
int trie[maxn][26];
//bool isw[maxn];查询整个单词用
void insert(char *s,int rt)
{
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';
        if(trie[rt][x]==0)//现在插入的字母在之前同一节点处未出现过 
        {
            trie[rt][x]=++tot;//字母插入一个新的位置，否则不做处理 
        }
        rt=trie[rt][x];//为下个字母的插入做准备  
    }
    /*isw[rt]=true;标志该单词末位字母的尾结点，在查询整个单词时用到*/
}
bool find(char *s,int rt)
{
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';
        if(trie[rt][x]==0)return false;//以rt为头结点的x字母不存在，返回0 
        rt=trie[rt][x];//为查询下个字母做准备 
    }
    return true;
    //查询整个单词时，应该return isw[rt] 
}
char s[22];
int main()
{
    tot=0;
    int rt=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert(s,rt);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        if(find(s,rt))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

字典树完整模板2：查询前缀出现次数

//字典树完整模板2，查询前缀出现次数
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int trie[400001][26],len,root,tot,sum[400001];
bool p;
int n,m; 
char s[11];
void insert()
{
    len=strlen(s);
    root=0;
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(!trie[root][id]) trie[root][id]=++tot;
        sum[trie[root][id]]++;//前缀后移一个位置保存 
        root=trie[root][id];
    }
}
int search()
{
    root=0;
    len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(!trie[root][id]) return 0;
        root=trie[root][id];
    }//root经过此循环后变成前缀最后一个字母所在位置的后一个位置 
    return sum[root];//因为前缀后移了一个保存，所以此时的sum[root]就是要求的前缀出现的次数 
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert();
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin>>s;
        printf("%d\n",search());
    }
}

字典树模板指针写法：

//字典树模板指针写法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char s[11];
int n,m;
bool p;
struct node
{
    int count;
    node * next[26];
}*root;
node * build()
{
    node * k=new(node);
    k->count=0;
    memset(k->next,0,sizeof(k->next));
    return k;
}
void insert()
{
    node * r=root;
    char * word=s;
     while(*word)
    {
        int id=*word-'a';
        if(r->next[id]==NULL) r->next[id]=build();
        r=r->next[id];
        r->count++;
        word++;
    }
}
int search()
{
    node * r=root;
    char * word=s;
    while(*word)
    {
        int id=*word-'a';
        r=r->next[id];
        if(r==NULL) return 0;
        word++;
    }
    return r->count;
}
int main()
{
    root=build();
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
            cin>>s;
            insert();
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin>>s;
        printf("%d\n",search());
    }
}

manacher模板：求字符串中最长回文串长度

//manacher模板，求字符串中最长回文串长度
const int maxn=1000010;
char MA[maxn<<1];
int MP[maxn<<1];
void Manacher(char s[],int len)
{
    int l=0;
    MA[l++]='$';
    MA[l++]='#';
    for(int i=0;i<len;i++)
    {
        MA[l++]=s[i];
        MA[l++]='#';
    }
    MA[l]=0;
    int mx=0,id=0;
    for(int i=0;i<l;i++)
    {
        MP[i]=mx>i?min(MP[2*id-i],mx-i):1;
        while(MA[i+MP[i]]==MA[i-MP[i]])
            MP[i]++;
        if(i+MP[i]>mx)
        {
            mx=i+MP[i];
            id=i;
        }
    }
}
char s[maxn];
 
int main()
{
    while(scanf("%s",s)!=EOF)
    {
        int len=strlen(s);
        Manacher(s,len);
        int ans=0;
        for(int i=0;i<2*len+2;i++)
            ans=max(ans,MP[i]-1);
        printf("%d\n",ans);
    }
    return 0;
}

这篇关于模板整理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

模板整理

KMP模板：

KMP模板1：简单的字符串匹配

KMP模板2：求模式串在待匹配串中的出现次数（不重复）

KMP模板3：求模式串在待匹配串中的出现次数（可重复）

字符串循环节长度为：len - next[len] ;（len为字符串长度）//跑一个next数组即可

字典树模板：插入和查找

字典树完整模板1：查询前缀（或整个单词）是否出现

字典树完整模板2：查询前缀出现次数

字典树模板指针写法：

manacher模板：求字符串中最长回文串长度

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

模板整理

KMP模板：

KMP模板1：简单的字符串匹配

KMP模板2：求模式串在待匹配串中的出现次数（不重复）

KMP模板3：求模式串在待匹配串中的出现次数（可重复）

字符串循环节长度为 ：len - next[len] ;（len为字符串长度）//跑一个next数组即可

字典树模板： 插入和查找

字典树完整模板1：查询前缀（或整个单词）是否出现

字典树完整模板2：查询前缀出现次数

字典树模板指针写法：

manacher模板：求字符串中最长回文串长度

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

字符串循环节长度为：len - next[len] ;（len为字符串长度）//跑一个next数组即可

字典树模板：插入和查找