线性数据结构（二）

邻接表

$\textbf{Hash}$ 函数，图论中经常使用邻接表，下面以图论为例子
插入边 $(x, y, z)$ 的时候，如何用邻接表实现

void add(int x, int y, int z) {
    ver[++tot] = y, edges[tot] = z;
    next[tot] = head[x], head[x] = tot;
}

void solve() {
    for (int i = head[x]; i; i = next[i]) {
        int y = ver[i], z = edges[i];
    }
}

哈希

hash
algorithm

$H(x) = (x \bmod P) + 1 \quad P \ \text{是一个素数}$

考虑插入序列中的一个数 $A_i$

$\textbf{head}[H(A_i)]$ 定位到这个链表
在这个链表中查找是否存在 $A_i$ $A_{i}$
- $\textbf{if}$ 存在， $\textbf{count}[A_i] + 1$
- $\textbf{else}$ ，将 $A_i$ 插入表头

对于序列来说，用 Hash 表一般保存的是数据的下标
下面以状态压缩为例，阐述一下状态哈希

const int P = 1000003;
int head[P], next[P];
void init() { memset(head, 0, sizeof head); }

int H(State &s) {
    int v;
    for (int i = 0; i < 9; i++) v = v*10 + s[i];
    return v % P;
}
int insert(int s) {
    int h = H(st[s]);
    for (int i = head[h]; i; i = next[i]) {
        if (memcmp(st[i], st[s], sizeof st[s]) == 0) return 0;
    }
    next[s] = head[h], head[h] = s;
    return 1;
}

Acwing137
定义 $\textbf{Hash}$ 函数，对于某一片雪花 $a_i [\cdots]$

$H(a_i[1\cdots 6]) = \left( \sum_{j=1}^{6}a_{i,j} + \prod_{j=1}^{6}a_{i, j} \right) \bmod P$

$a(i, i+1, \cdots i+5), b(i, i+1, \cdots i+5)$
$\textbf{for} \ \forall i, j:\quad \textbf{equal}(a_i[\cdots], b_j[\cdots])$
对每片雪花，依次插入 $\textbf{Hash}$ 表即可

const int maxn = 100000 + 10;
const int P = 99991;
int n, tot = 0, snow[maxn][6], head[maxn], nxt[maxn];

inline int Hash(const int *a) {
    int mul = 1, sum = 0;
    for (int i = 0; i < 6; i++) {
        sum = (sum + a[i]) % P;
        mul = (ll) mul * a[i] % P;
    }
    return (sum + mul) % P;
}

int equal(const int *a, const int *b) {
    _for(i, 0, 6) _for(j, 0, 6) {
        bool ok = 1;
        for (int k = 0; k < 6; k++) {
            if (a[(i+k)%6] != b[(j+k)%6]) ok = 0;
        }
        if (ok) return 1;
        ok = 1;
        for (int k = 0; k < 6; k++) {
            if (a[(i+k)%6] != b[(j-k+6)%6]) ok = 0;
        }
        if (ok) return true;
    }
    return false;
}

int insert(const int *a) {
    int h = Hash(a);
    for (int i = head[h]; i; i = nxt[i]) {
        if (equal(snow[i], a)) return 0;
    }
    ++tot;
    memcpy(snow[tot], a, 6 * sizeof(int));
    nxt[tot] = head[h], head[h] = tot;
    return 1;
}

int main() {
    freopen("input.txt", "r", stdin);

    cin >> n;
    for (int i = 0; i < n; i++) {
        int a[7];
        for (int j = 0; j < 6; j++) scanf("%d", &a[j]);
        if (!insert(a)) {
            puts("Twin snowflakes found.");
            return 0;
        }
    }
    puts("No two snowflakes are alike.");
    return 0;
}

字符串哈希

strHash

algorithm
取 $P=131$ 或者 $P = 13331$

在字符串 $S$ 后面加一个字符 $c$
$H(S+c) = (H(S) \cdot P + val[c]) \bmod M$
字符串 $S$ 的 $\textbf{Hash}$ 值为 $H(S)$
字符串 $S + T$ 的 $\textbf{Hash}$ 值为 $H(S+T)$
可以推出字符串 $T$ 的 $\textbf{Hash}$ 值为
（相当于将字符串 $S$ 在 $P$ 进制下左移 $len(T)$ 位）
$H(T) = (H(S+T) - H(S) \cdot P^{len(T)}) \bmod M$
字符串 $\textbf{Hash}$ $Hash$ 中的前缀哈希
- 对于前缀子串 $S[1\cdots i]$
  $H(i) = H(i-1) \cdot P + (S[i])$
- 对于任意区间 $[l, r]$
  $H(\ [l\cdots r] \ ) = H(r) - H(l-1) * P^{r-l+1}$

typedef unsigned long long ull;
const int maxn = 1000010, P = 131;

char str[maxn];
ull H[maxn], pwr[maxn];
int n, m;

ull get(int l, int r) {
    return H[r] - H[l-1] * pwr[r-l+1];
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%s", str + 1);
    n = strlen(str + 1);

    pwr[0] = 1;
    for (int i = 1; i <= n; i++) {
        H[i] = H[i-1] * P + str[i] - 'a' + 1;
        pwr[i] = pwr[i-1] * P;
    }

    int m;
    scanf("%d", &m);
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
}

字符串哈希求最长回文串

Acwing139

$\textbf{for} \ \forall i \in [1, n]$ 枚举每个中心点
二分回文半径 $r$ $r$ ，判断 $[i-mid, i-1]$ $[i - m i d, i - 1]$ 和 $[i+1, i+mid]$ $[i + 1, i + m i d]$ 是否满足回文？
- $\textbf{if}$ 满足回文性质，扩大半径
- $\textbf{else}$ 减少半径

typedef unsigned long long ull;
const int maxn = 2000000 + 10, P = 131;
char str[maxn];
int n;
ull hl[maxn], hr[maxn], p[maxn];

void prework() {
    for (int i = n*2; i >= 1; i -= 2) {
        str[i] = str[i/2];
        str[i-1] = 'z' + 1;
    }
    n *= 2;

    p[0] = 1;
    for (int i = 1, j = n; i <= n; i++, j--) {
        hl[i] = hl[i-1] * P + str[i] - 'a' + 1;
        hr[i] = hr[i-1] * P + str[j] - 'a' + 1;
        p[i] = p[i-1] * P;
    }
}

ull get(const ull h[], int l, int r) {
    return h[r] - h[l-1] * p[r-l+1];
}

void solve() {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = 0, r = min(i-1, n-i);
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (get(hl, i-mid, i-1) != get(hr, n+1-(i+mid), n+1-(i+1))) r = mid - 1;
            else l = mid;
        }
        // ans is l
        if (str[i-l] <= 'z') ans = max(ans, l+1);
        else ans = max(ans, l);
    }
    printf("%d\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%s", str+1) && str[1] != 'E') {
        n = strlen(str+1);
        printf("Case %d: ", ++kase);

        // prework
        prework();

        // then solve
        solve();
    }
}

字符串哈希求 LCP

$\textbf{algorithm}$
$\textbf{Hash}(i, L), \ \textbf{Hash}(j, L)$ 分别表示
从 $i, j$ 出发，长度为 $L$ 的子串哈希
二分答案 $L$ ，如果子串 $[i, i+mid-1]$ ， $[j, j+mid-1]$
哈希不相等，那么尝试减小 $L$ ，否则增大 $L$

int LCP(int i, int j) {
    int l = 0, r = min(n-i+1, n-j+1);
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (get(i, i+mid-1) != get(j, j+mid-1)) r = mid - 1;
        else l = mid;
    }
    return l;
}

// 后缀数组也可以求出来
inline bool cmp(int i, int j) {
    int len = LCP(i, j);
    int ival = i + len > n ? INT_MIN : str[i+len];
    int jval = j + len > n ? INT_MIN : str[j+len];
    return ival < jval;
}
sort(sa+1, sa+1+n, cmp)

UVALive4513

typedef unsigned long long ull;
typedef pair<ull, int> PII;
const int maxn = 40000 + 10;
char str[maxn];
const int P = 131;
ull h[maxn], p[maxn];
int n, m, pos;

void prework() {
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * P + str[i] - 'a' + 1;
        p[i] = p[i-1] * P;
    }
}

ull get(int l, int r) {
    return h[r] - h[l-1] * p[r-l+1];
}

int check(int L, int &pos) {
    pos = -1;
    PII a[maxn];
    for (int i = 1; i <= n-L+1; i++) {
        ull x = get(i, i+L-1);
        a[i] = make_pair(x, i);
    }
    sort(a+1, a+n-L+2);

    int cnt = 0;
    for (int i = 1; i <= n-L+1; i++) {
        if (i == 1 || (a[i].first != a[i-1].first)) cnt = 0;
        if (++cnt >= m) pos = max(pos, a[i].second);
    }

    return pos > 0;
}

void solve() {
    int pos = -1;
    if (!check(1, pos)) {
        puts("none");
        return;
    }

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (!check(mid, pos)) r = mid - 1;
        else l = mid;
    }
    // l is the answer
    check(l, pos);
    printf("%d %d\n", l, pos-1);
    return;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &m) == 1 && m) {
        scanf("%s", str+1);
        n = strlen(str+1);

        // then prework
        prework();
        // then solve
        solve();
    }
}