Java教程
模板整理
本文主要是介绍模板整理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
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;
}
这篇关于模板整理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
后台交互资料入门指南11-14
-
如何轻松创建项目环境：新手入门教程11-14
-
如何抽离公共代码：初级开发者指南11-14
-
Python编程入门指南11-14
-
Python编程入门：如何获取参数11-14
-
JWT 用户校验：简单教程与实践11-14
-
Pre-commit 自动化测试入门指南11-14
-
Python编程基础11-14
-
Server Action入门教程：轻松掌握服务器操作11-14
-
Server Component入门教程：轻松搭建服务器组件11-14
-
用useRequest实现数据请求的简单教程11-14
-
RestfulAPI课程：初学者的全面指南11-14
-
Server Action课程：入门级教程11-14
-
Server Component课程入门指南11-14
-
dnd-kit学习：初学者指南11-14
栏目导航
