Description
在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。
一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。
一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。
下面，给两个小写字母串A，B，请你计算：
(1) A的一个最短的子串，它不是B的子串
(2) A的一个最短的子串，它不是B的子序列
(3) A的一个最短的子序列，它不是B的子串
(4) A的一个最短的子序列，它不是B的子序列
Input
有两行，每行一个小写字母组成的字符串，分别代表A和B。
Output
输出4行，每行一个整数，表示以上4个问题的答案的长度。如果没有符合要求的答案，输出-1.
Sample Input
aabbcc abcabc
Sample Output
2 4 2 4
HINT
对于100%的数据，A和B的长度都不超过2000
题解
如果都是子串，那么直接在后缀自动机上BFS即可；否则，可以乱搞出什么“子序列自动机”（只需要把每个节点连到它的下一个a、下一个b、...下一个z即可），然后bfs。
（为了一句last=ne调了一个小时QAQ）
附代码：
#include#include #include #include #include const int N = 4050;struct Node{ int nxt[26], pa, len;};struct Automation{ Node nodes[N]; int cnt; inline int newNode(int l = 0) { memcpy(&nodes[cnt].nxt, &nodes[l].nxt, sizeof(int) * 26); nodes[cnt].pa = nodes[l].pa; nodes[cnt].len = nodes[l].len; return cnt++; } int root; int seq_last[26], last; void init() { memset(&nodes[0], 0, sizeof(Node)); cnt = 1; root = newNode(); for (int i = 0; i < 26; ++i) seq_last[i] = root; last = root; } void seq_append(int x) { int ne = newNode(); for (int i = 0; i < 26; ++i) for (int q = seq_last[i]; q && !nodes[q].nxt[x]; q = nodes[q].pa) nodes[q].nxt[x] = ne; nodes[ne].pa = seq_last[x]; seq_last[x] = ne; } void suffix_append(int x) { int ne = newNode(); nodes[ne].len = nodes[last].len + 1; int q = last; while (q && !nodes[q].nxt[x]) { nodes[q].nxt[x] = ne; q = nodes[q].pa; } if (!q) { nodes[last = ne].pa = root; return; } int p = nodes[q].nxt[x]; if (nodes[p].len == nodes[q].len + 1) { nodes[last = ne].pa = p; return; } int pq = newNode(p); nodes[pq].len = nodes[q].len + 1; nodes[last = ne].pa = nodes[p].pa = pq; while (q && nodes[q].nxt[x] == p) { nodes[q].nxt[x] = pq; q = nodes[q].pa; } }};struct AAA{ int x, y, len; AAA(int a, int b, int c) : x(a), y(b), len(c) {}};std::bitset vis[N];std::queue Q;int bfs(const Automation &A, const Automation &B) { while (!Q.empty()) Q.pop(); Q.push(AAA(A.root, B.root, 0)); for (int i = 0; i < A.cnt; ++i) vis[i].reset(); vis[A.root][B.root] = 1; while (!Q.empty()) { AAA x = Q.front(); Q.pop(); const Node &a = A.nodes[x.x], &b = B.nodes[x.y]; for (int i = 0; i < 26; ++i) { int l = a.nxt[i], r = b.nxt[i]; if (!l) continue; if (!r) return x.len + 1; if (!vis[l][r]) Q.push(AAA(l, r, x.len + 1)); vis[l][r] = 1; } } return -1;}Automation a, b;char s[N], p[N];int main() { scanf("%s%s", s, p); a.init(); for (char *r = s; *r; ++r) a.suffix_append(*r - 'a'); b.init(); for (char *r = p; *r; ++r) b.suffix_append(*r - 'a'); printf("%d\n", bfs(a, b)); b.init(); for (char *r = p; *r; ++r) b.seq_append(*r - 'a'); printf("%d\n", bfs(a, b)); a.init(); for (char *r = s; *r; ++r) a.seq_append(*r - 'a'); int ans4 = bfs(a, b); b.init(); for (char *r = p; *r; ++r) b.suffix_append(*r - 'a'); printf("%d\n", bfs(a, b)); printf("%d\n", ans4); return 0;}