当前位置: 首页> 健康> 母婴 > 首页页面设计_网站建设设计制作方案与价格_怎么免费创建个人网站_seo优化服务价格

首页页面设计_网站建设设计制作方案与价格_怎么免费创建个人网站_seo优化服务价格

时间:2025/7/11 19:47:22来源:https://blog.csdn.net/daihaoweikevin/article/details/143173717 浏览次数:0次
首页页面设计_网站建设设计制作方案与价格_怎么免费创建个人网站_seo优化服务价格

前置知识:?有吗,不知道哎。

但是最好学一下字符串哈希。

字符串哈希

用于比较两个字符串是否相同。

原理:和普通哈希相似,只是将字符串转换为了一个 b a s e base base 进制的数,然后使用哈希的处理方法,对其取模存储,然后通过加上一个大质数的方法来解决冲突。一般我使用的 b a s e base base 13331 13331 13331,取模的数为 1 e 9 + 7 1e9+7 1e9+7 1 e 18 + 7 1e18+7 1e18+7

实现:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[10005],k,ans;
const int BASE=13331;
const int mod=1e18+7;
const int prime =233317;
int get_hash(char s[])
{int h=0;int len=strlen(s);for(int i=0;i<=len-1;i++)h=(1ll*h*BASE+s[i])%mod+prime;return h;
}
signed main()
{cin>>n;for(int i=1;i<=n;i++){char s[10005];cin>>s;a[++k]=get_hash(s);}sort(a+1,a+1+n);for(int i=1;i<=k;i++)if(a[i]!=a[i-1])ans++;cout<<ans<<'\n';return 0;
}

正文

假设有两串字符串

A : a a b a b a a b a a A: aababaabaa A:aababaabaa

B : a a b a a B:aabaa B:aabaa

需要在 A A A 中寻找 子串 B B B

我们首先需要处理一个东西,叫做 b o r d e r border border ,我习惯叫他为 n e x t next next 数组,具体之后解释。

这个数组中应该要存什么呢? 由于我们知道暴力的写法为双指针每次匹配不对之后需要回退到开始的地方,效率低下,那么我们可以思考,在上述的例子中, A A A 序列中我们匹配到第 4 4 4 个字符(从 0 0 0 开始)继续匹配会发现匹配失败,暴力写法就会回退到第 0 0 0 个字符,显然,之后会有几次匹配是显然不成立的。

经过观察们可以发现,最佳的方案是失败后直接从第 3 3 3 个字符开始,那么如何回退到那里呢?

这就要用到 n e x t next next 数组了。 n e x t [ i ] next[i] next[i] 存的是子串中到第 i i i 个字符为止,子串中最长的公共前后缀长度,在 B B B n e x t next next 数组为 01012 0 1 0 1 2 01012 。这个可以使用双指针快速的预处理。所以我们知道了,当我们在第 j j j 个字符匹配失败的时候,只需要回退到 n e x t [ j − 1 ] next[j-1] next[j1] 即可,效率显著提升。

附上最快乐的代码

#include<bits/stdc++.h>
const int N=1e6+5;
using namespace std;
int nxt[N];
int lena,lenb,j; 
char a[N],b[N];
int main()
{cin>>a+1;cin>>b+1;lena=strlen(a+1);lenb=strlen(b+1);j=0;for(int i=2;i<=lenb;i++)//处理前缀表{     while(j&&b[i]!=b[j+1])j=nxt[j];   //不相等结束 if(b[j+1]==b[i])//相等后指针前移j++;    nxt[i]=j;}j=0;for(int i=1;i<=lena;i++)//暴力+KMP优化回退{while(j>0&&b[j+1]!=a[i])//不相等回退j=nxt[j];if(b[j+1]==a[i]) //相等后指针前移  j++;if(j==lenb){cout<<i-lenb+1<<"\n";j=nxt[j];}}for(int i=1;i<=lenb;i++)//打印前缀表cout<<nxt[i]<<" ";return 0;
}

如有问题欢迎指出。

关键字:首页页面设计_网站建设设计制作方案与价格_怎么免费创建个人网站_seo优化服务价格

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: