-
字符串哈希
字符串哈希就是一个字符串到一个整数的映射，常用于比较两个字符串是否相等。
map大法好
set大法好
hash值相等两个字符串大概率相等。
hash值不等两个字符串一定不相等。
一般采取神奇的RK算法。
RK-hash 就是把一个字符串看作一个 base 进制的大整数，然后对一个
素数 p 取模。
hash[i]=(hash[i-1] * base+s[i])%p
base 可以取 31,131,13131 等，大于 |Σ| 即可。
注意要把 a 看作 1 而不是 0。
p 一定要是 long long 范围的一个素数，比如23333333333333333,10^18 + 9。
unsigned long long 自然溢出可以看作是对 2^64 取模，但是可以被特殊
构造卡掉。
不放心可以多找几个素数同时算。
瞎jb哈希才是最好玩的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 10005
#define seed 20020207
#define ULL unsigned long long
using namespace std;
int n;
long long h[MAXN];
string s[MAXN];
ULL hash(string s) {
ULL value=0;
int x=1;
for(int i=0;i<s.length();i++) {
value+=s[i]*x*seed;
x*=10;
}
return value;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
cin>>s[i];
h[i]=hash(s[i]);
}
int ans=0;
sort(h+1,h+n+1);
for(int i=1;i<=n;i++) {
if(h[i]!=h[i+1]) ans++;
}
printf("%d",ans);
return 0;
}
-
KMP
KMP 是一个常用的单模式串匹配算法。
简单来说就是求B串在A串中能否匹配或者匹配到哪个位置。
next 数组?最长的后缀等于前缀的位置。
next 数组求法?自己与稍短一些的自己匹配。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=1001;
int Next[maxn];
vector<int> Ans;
inline void Get_Next(string s) {
int l=s.length(),t;
Next[0]=-1;
for(int i=1;i<l;++i) {
t=Next[i-1];
while(s[t+1]!=s[i]&&t>=0)
t=Next[t];
if(s[t+1]==s[i])
Next[i]=t+1;
else
Next[i]=-1;
}
}
inline void KMP(string s1,string s2) {
Get_Next(s2);
int l1=s1.length();
int l2=s2.length();
int i=0,j=0;
while(j<l1) {
if(s2[i]==s1[j]) {
++i;++j;
if(i==l2) {
Ans.push_back(j-l2+1);
i=Next[i-1]+1;
}
}
else {
if(i==0)
j++;
else
i=Next[i-1]+1;
}
}
}
int main() {
string s1,s2;
int l;
cin>>s1>>s2;
l=s2.length();
KMP(s1,s2);
for(int i=0;i<Ans.size();++i)
printf("%d\n",Ans[i]);
for(int i=0;i<l;++i)
printf("%d ",Next[i]+1);
return 0;
}
扩展KMP
-
AC自动机（Trie图）
由于AC自动机是基于Trie树的，所以顺便复习一下Trie树。
多模式串匹配
把 Trie 树上不存在的孩子用它 fail 节点的孩子补出来。
fail 节点的概念与 KMP 的 next 类似。
可以用一次 bfs 来求出。
若 trie[i][x] 存在，则 fail[trie[i][x]]=trie[fail[i]][x]。
否则，trie[i][x]=trie[fail[i]][x]。
没有 KMP 用单串 AC 自动机替代。(雾
简单来说AC自动机就是在Trie树上跑KMP。
//求有多少模式串在文本串里出现过
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct Trie {
int ch[26];
int end;
int fail;
}AC[1000000];
int cnt=0;
int index(char c) {
return c-'a';
}
void Build_Trie(string s) {
int l=s.length();
int now=0;
for(int i=0;i<l;i++) {
int id=index(s[i]);
if(AC[now].ch[id]==0) {
AC[now].ch[id]=++cnt;
}
now=AC[now].ch[id];
}
AC[now].end++;
}
void Get_fail() {
queue<int> q;
for(int i=0;i<26;i++) {
if(AC[0].ch[i]!=0) {
AC[AC[0].ch[i]].fail=0;
q.push(AC[0].ch[i]);
}
}
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0;i<26;i++) {
if(AC[u].ch[i]!=0) {
AC[AC[u].ch[i]].fail=AC[AC[u].fail].ch[i];
q.push(AC[u].ch[i]);
}
else
AC[u].ch[i]=AC[AC[u].fail].ch[i];
}
}
}
int AC_work(string s) {
int l=s.length();
int now=0,ans=0;
for(int i=0;i<l;i++) {
now=AC[now].ch[index(s[i])];
for(int j=now;j && AC[j].end!=-1;j=AC[j].fail) {
ans+=AC[j].end;
AC[j].end=-1;
}
}
return ans;
}
int main() {
int n;
string s;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
cin>>s;
Build_Trie(s);
}
Get_fail();
cin>>s;
printf("%d",AC_work(s));
return 0;
}
-
Manacher
Manacher 是一个处理回文串的算法。
首先加一个小优化，就是在每个字符的间隔（包括头尾）添加特殊字符（如*），然后每个字符串的长度都会变成奇数，处理起来方便了许多，为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题。
a b c d e ->$ * a * b * c * d * e *
记录 p[ i ] 表示从 i 这个点能满足回文向两边最大扩展的距离（包括 i ），这样每一个回文串就确定了。
我们假设 p[1 ~ i-1] 已经求好了，现在要求 p[ i ]：
假设之前能到的最右断点是 R ，对应的中点是 pos ，j 是 i 的对称点。
1.当i＜R时
由于L~R是回文，所以p[ i ] = p[ j ]（i的最长回文和j的最长回文相同）。
这种情况是另一种：j 的最长回文跳出 L 了。那么 i 的最长回文就不一定是 j 的最长回文了，但蓝色的肯定还是满足的。
综上所述，p[ i ] = min(p[ 2 * pos-i ], R-i )。
由于R是递增的，所以时间复杂度为O（n）。
一个串的本质不同的回文串个数不超过 n 个。
void manacher {
scanf("%s",s+1);
n=strlen(s+1);
for(i=n;i>=1;i--)
s[i*2]=s[i];
for(i=1;i<=n*2+1;i+=2)
s[i]='*';
s[0]='$';
m=n*2+1;
R=pos=0;
for(i=1;i<=m;i++) {
if(R<i) {
p[i]=0;
for(;s[i+p[i]+1]==s[i-p[i]-1];p[i]++);
R=p[i]+i;
pos=i;
continue;
}
j=pos*2-i;
if(i+p[j]<R) {
p[i]=p[j];
continue;
}
p[i]=R-i;
for(;s[i+p[i]+1]==s[i-p[i]-1];p[i]++);
R=p[i]+i;
pos=i;
}
}
-
后缀数组
