哈希
cpp
struct StrHash{
int MOD,BASE,n;
vector<int> p,h;
StrHash(int n_=0){
randing();
init(n_);
}
StrHash(string s){
randing();
init(s.size());
work(s);
}
void init(int n_){
n=n_+1;
p.assign(n, int{});
h.assign(n, int{});
p[0]=1;
h[0]=0;
}
void randing(){
srand(time(0));
MOD = 998244353 + rand() % 10008;
BASE = 33 + rand() % 234;
}
void work(string s){
for(int i=1;i<n;i++){
p[i] = ((long long)p[i - 1] * BASE) % MOD;
h[i]=((long long)h[i-1]*BASE+s[i-1]-'a')%MOD;
}
}
int get(int l,int r){
return (h[r] - (long long) h[l-1] * p[r-l+1] % MOD + MOD) % MOD;
}
};
KMP
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int pmt[MAXN];
void get_pmt(const string& s) {
for (int i = 1, j = 0; i < s.length(); ++i) {
while (j && s[i] != s[j]) j = pmt[j - 1];
if (s[i] == s[j]) j++;
pmt[i] = j;
}
}
void kmp(const string& s, const string& p) {
for (int i = 0, j = 0; i < s.length(); ++i) {
while (j && s[i] != p[j]) j = pmt[j - 1];
if (s[i] == p[j]) j++;
if (j == p.length()) {
cout << i - j + 2 << '\n'; // 因为要1-index,所以是+2
j = pmt[j - 1];
}
}
}
int main() {
ios::sync_with_stdio(false);
string s, p;
cin >> s >> p;
get_pi(p);
kmp(s, p);
for (int i = 0; i < p.length(); ++i)
cout << pmt[i] << ' ';
return 0;
}
最小表示法
cpp
int n=read();
int a[n*2];
For(i,0,n){
a[i]=read();
a[i+n]=a[i];
}
int i=0,j=1,k=0;
while(i<n&&j<n){
while(a[i+k]==a[j+k])k++;
if(a[i+k]>a[j+k])i+=k+1;
else j+=k+1;
k=0;
if(i==j)j++;
}
int st=min(i,j);
For(i,st,st+n){
char f=' ';
if(i==st+n-1)f=endl;
cout<<a[i]<<f;
}
字典树
cpp
const int N=3e5+5;
int nxt[N][26][2];
int cnt = 0;
string s;
For(i, 0, n)
{
cin >> s;
int cur = 0;
for (int i = 0; i < s.size(); i++)
{
int c = s[i] - 'a';
if (!nxt[cur][c][0])
{
nxt[cur][c][0] = ++cnt;
}
nxt[cur][c][1]++;
cur = nxt[cur][c][0];
}
}
Z函数
cpp
std::vector<int> zFunction(std::string s) {
int n = s.size();
std::vector<int> z(n + 1);
z[0] = n;
for (int i = 1, j = 1; i < n; i++) {
z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] > j + z[j]) {
j = i;
}
}
return z;
}