1 字符串最小表示法
void get_min(char s[]){
int n = strlen(s + 1);
for(int i = 1; i <= n; i++) s[i + n] = s[i];
int i = 1, j = 2, k;
while(i <= n && j <= n){
for(k = 0; k < n && s[i + k] == b[j + k]; k++);
if(k == n) break;
if(s[i + k] > s[j + k]) {
i += k + 1;
if(i == j) i++;
}
else {
j += k + 1;
if(i == j) j++;
}
}
k = min(i, j);
for(i = 0; i < n; i++) s[i] = s[i + k];
}
2 字符串Hash
typedef unsigned long long ULL;
const int N = 2e5+5, base = 131;
char str[N];
ULL h[N], p[N];
int m, n;
ULL get(int l, int r){
return h[r] - h[l-1] * p[r-l+1];
}
void hash(){
p[0] = 1;
for(int i = 1; i <= n; i++){
h[i] = h[i-1] * base + str[i-1] - 'a' + 1;
p[i] = p[i-1] * base;
}
}
3 字符串匹配 KMP
void get_next(char s[], int *Next, int n) {
int i = 1, j = 0;
Next[1] = 0;
while (i < n) {
if (j == 0 || s[i - 1] == s[j - 1]) {
++i;
++j;
Next[i] = j;
} else j = Next[j];
}
}
int kmp(char s[], char t[], int pos) {
int m = strlen(s), n = strlen(t);
int *Next = new int[n + 1];
get_next(t, Next, n);
int i = pos + 1, j = 1;
while (i <= m && j <= n) {
if (j == 0 || s[i - 1] == t[j - 1]) ++i, ++j;
else j = Next[j];
}
if (j > n) return i - n - 1;
return -1;
}
