字符串算法总结整理 以前学习的做的笔记，现在整理一下发出来 字符串哈希 字典树 KMP next数组 板子 扩展KMP Manacher 字符串哈希 常用BKDRHash unsigned int BKDRHash(char *str) { unsigned int seed = 31, key = 0; while (*str) key = key * seed + (*str++); return key & 0x7fffffff; } ull base[maxn]; ull Hash[maxn]; base[0] = 1; for (int i = 1; i <= len; i++) base[i] = base[i - 1] * seed; Hash[0] = s[0] - 'a' + 1; for (int i = 1; i < len; i++) Hash[i] = Hash[i - 1] * seed + s[i] - 'a' + 1; 字典树 map使用:略 压缩空间字典树 int trie[maxn][26]; int num[maxn] = {0}; int pos = 1; void insert(char str[]) { int p = 0; for (int i = 0; str[i]; i++) { int n = str[i] - 'a'; if (trie[p][n] == 0) trie[p][n] = pos++; p = trie[p][n]; num[p]++; } } int find(char str[]) { int p = 0; for (int i = 0; str[i]; i++) { int n = str[i] - 'a'; if (trie[p][n] == 0) return 0; p = trie[p][n]; } } KMP KMP解决的是字符串匹配问题： 一个文本串S，一个模式串P，求P在S中出现的次数 next数组 next[i]为满足P[i-z ~ i-1] = P[0 ~ z-1] 的最大z值 next数组的含义：当前字符以前的字符串中，有多大长度的相同前缀和后缀 P[i-next[i]...i-1] = P[0 ... next[i] - 1] P[] A B C D A B D   next[] -1 0 0 0 0 1 2 0 void kmp_pre(char s[], int m, int next[]) { int i = 0, j = next[0] = -1; while (i < m) { while (j != -1 && x[i] != x[j]) j = next[j]; next[++i] = ++j; } } next数组的深入理解和应用： 沿着next数组一直往前后，得到的是所有前缀，也是当前后缀的字符串。 ABCABCABCAB -> ABCABCAB -> ABCAB -> AB P[] A B C A B C A B C A B   next[] -1 0 0 0 1 2 3 4 5 6 7 8 周期性字符串：n % (n-next[n]) == 0，循环节长度为n-nxet[n] next[]往前跳的步长是一样的，除了最后一次 板子 x[]为模式串, y[]为主串 int kmp_count(char x[], int m, char y[], int n) { int i = 0, j = 0, ans = 0; kmp_pre(x, m, next); while (i < n) { while (j != -1 && y[i] != x[j]) j = next[j]; i++; j++; if (j >= m) { ans++; j = next[j]; } } return ans; } 扩展KMP next[i]: x[i..m-1]与x[0...m-1]的最长公共前缀 extend[i]: y[i..n-1]与y[0///m-1]的最长公共前缀 例: y = "aaaaabbb" x = "aaaaac" next[] = {6, 4, 3, 2, 1, 0} extend[] = {5, 4, 3, 2, 1, 0, 0, 0} Manacher 求解问题：给定一个字符串s，找到s中最长的回文子字符串。 引入： 原串：abaaba 修改后的子串：$#a#b#a#a#b#a# 统一奇数长度和偶数长度的回文串，给所有字串一个中心 然后计算回文半径 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 修改后Ma[] $ # a # b # a # a # b # a # 回文半径Mp[] 1 1 2 1 4 1 2 7 2 1 4 1 2 1 Ma[i-Mp[i] ~ i+Mp[i]]是回文串 $符号可简化边界判断 算法步骤: 预处理得到字符串Ma 充分利用前面的信息得到数组Mp 时间复杂度和空间复杂度都是O(n) void Manacher(char s[], int len) { int l = 0; Ma[l++] = '$'; Ma[l++] = '#'; for (int i = 0; i < l; i++) { Ma[l++] = s[i]; Ma[l++] = '#'; } Ma[l] = 0; int mx = 0, id = 0; for (int i = 0; i < l; i++) { Mp[i] = mx > i ? min(Mp[2*id-i], mx - i) : 1; while (Ma[i+Mp[i]] == Ma[i-Mp[i]]) Mp[i]++; if (i = Mp[i] > mx) { mx = i + Mp[i]; id = i; } } }