字符串
CCDV2
8月 13, 2018
KMP
//s为文本串，t为待匹配串 //下标从0开始 const int MAXM = 2e3 + 5; char s[MAXM], t[MAXM]; int nxt[MAXM], n, m; void getNext(char t[]) { int len = strlen(t); nxt[0] = -1; int i = 0, j = -1; while(i < len) { if(j == -1 || t[i] == t[j]) nxt[++i] = ++j; else j = nxt[j]; } } vector<int> pos; void kmp(char s[], char t[]) { int n = strlen(s); int m = strlen(t); for(int i = 0, j = 0; i < n; ++i) { if(j < n && s[i] == t[j]) { ++j; } else { while(j > 0) { j = nxt[j]; if(s[i] == t[j]) { ++j; break; } } } if(j == m) { pos.push_back(i - m + 1); } } }最小(最大)表示法
string s; int smallest(bool isSmall)//返回最小/最大表示法的起始下标 { int N = s.size(); s += s; int i = 0, p = 1; while(i < N && p < N) { int k = 0; while(s[i + k] == s[p + k]) ++k; if(k >= N) break; if(isSmall) { if(s[i + k] > s[p + k]) i = max(i + k + 1, p + 1); else p = max(p + k + 1, i + 1); } else { if(s[i + k] < s[p + k]) i = max(i + k + 1, p + 1); else p = max(p + k + 1, i + 1); } } return min(i, p); }最长回文子串
char s[MAXN], ma[MAXN * 2]; int len[4 * MAXN], n;//n = strlen(s) 初始的字符串长度 void Manacher() { int l = 0; ma[l++] = '$'; ma[l++] = '#'; for(int i = 0; i < n; ++i) { ma[l++] = s[i]; ma[l++] = '#'; } ma[l] = 0; int mx = 0, id = 0; for(int i = 0; i < l; ++i) { len[i] = mx > i ? min(len[2 * id - i], mx - i) : 1; while(ma[i + len[i]] == ma[i - len[i]]) len[i]++; if(i + len[i] > mx) { mx = i + len[i]; id = i; } } }- Trie树
单独考一个的不多。。而且也应该比较好写吧。。 - AC自动机
const int MAXNODE = 40; struct Trie { int next[MAXNODE][26], fail[MAXNODE], end[MAXNODE]; int root, L; int newnode() { for(int i = 0; i < 26; ++i) next[L][i] = -1; end[L++] = 0; return L - 1; } void init() { L = 0; root = newnode(); } void insert(char buf[]) { int len = strlen(buf); int now = root; for(int i = 0; i < len; ++i) { if(next[now][buf[i] - 'a'] == -1) next[now][buf[i] - 'a'] = newnode(); now = next[now][buf[i] - 'a']; } ++end[now]; } void build() { queue<int> q; fail[root] = root; for(int i = 0; i < 26; ++i) if(next[root][i] == -1) next[root][i] = root; else { fail[next[root][i]] = root; q.push(next[root][i]); } while(!q.empty()) { int now = q.front(); q.pop(); if(end[fail[now]]) end[now] = 1;// TODO 貌似并不是都需要这句话？ for(int i = 0;i < 26; ++i) if(next[now][i] == -1) next[now][i] = next[fail[now]][i]; else { fail[next[now][i]] = next[fail[now]][i]; q.push(next[now][i]); } } } int query(char buf[]) { int len = strlen(buf); int now = root; int res = 0; for(int i = 0; i < len; ++i) { now = next[now][buf[i] - 'a']; int temp = now; while(temp != root) { res += end[temp]; end[temp] = 0; temp = fail[temp]; } } return res; } } ac; 后缀数组
const int MAXN = 1e5 + 5; const int MAXL = 2e5 + 5; void radixSort(int *str, int *a, int *b, int n, int m) { static int count[MAXL]; memset(count, 0, sizeof(count)); for(int i = 0; i < n; ++i) ++count[str[a[i]]]; for(int i = 1; i <= m; ++i) count[i] += count[i - 1]; for(int i = n - 1; i >= 0; --i) b[--count[str[a[i]]]] = a[i]; } void getSA(int *str, int *sa, int n, int m) { static int rank[MAXL], a[MAXL], b[MAXL]; for(int i = 0; i < n; ++i) rank[i] = i; radixSort(str, rank, sa, n, m); rank[sa[0]] = 0; for(int i = 1; i < n; ++i) rank[sa[i]] = rank[sa[i - 1]] + (str[sa[i]] != str[sa[i - 1]]); for(int i = 0; (1 << i) < n; ++i) { for(int j = 0; j < n; ++j) { a[j] = rank[j] + 1; b[j] = j + (1 << i) >= n ? 0 : rank[j + (1 << i)] + 1; sa[j] = j; } radixSort(b, sa, rank, n, n); radixSort(a, rank, sa, n, n); rank[sa[0]] = 0; for(int j = 1; j < n; ++j) { rank[sa[j]] = rank[sa[j - 1]] + (a[sa[j - 1]] != a[sa[j]] || b[sa[j - 1]] != b[sa[j]]); } } } int s[MAXN], sa[MAXN], h[MAXN]; char buf[MAXN]; int rnk[MAXN]; void calcHeight(int *str, int *sa, int *h, int n) { int k = 0; h[0] = 0; for(int i = 1; i <= n; ++i) rnk[sa[i]] = i; for(int i = 0; i < n; ++i) { k = k == 0 ? 0 : k - 1; if(rnk[i] != 0) while(str[i + k] == str[sa[rnk[i] - 1] + k]) ++k; h[rnk[i]] = k; } } int main() { scanf("%s", buf); int len = strlen(buf); for(int i = 0; i < len; ++i) s[i] = buf[i] - 'a' + 1; s[len] = 0; getSA(s, sa, len + 1, 30);//仅小写字母情况下 calcHeight(s, sa, h, len); }