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

前置知识：？有吗，不知道哎。

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

字符串哈希

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

原理：和普通哈希相似，只是将字符串转换为了一个 $base$ 进制的数，然后使用哈希的处理方法，对其取模存储，然后通过加上一个大质数的方法来解决冲突。一般我使用的 $base$ 为 $13331$，取模的数为 $1e9+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:aababaabaa$

$B:aabaa$

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

我们首先需要处理一个东西，叫做 $border$ ，我习惯叫他为 $next$ 数组，具体之后解释。

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

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

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

附上最快乐的代码

#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;
}

如有问题欢迎指出。