题意：
下面，给两个小写字母串A，B，请你计算：
(1) A的一个最短的子串，它不是B的子串
(2) A的一个最短的子串，它不是B的子序列
(3) A的一个最短的子序列，它不是B的子串
(4) A的一个最短的子序列，它不是B的子序列
解：这是什么四合一毒瘤题......
先上正解：
第一问对B建后缀自动机，枚举A的每个前缀，在B上跑。
第二问枚举A中子串的开始位置，B中贪心匹配。O(n2)。
后两问分别建出B的后缀自动机和序列自动机，然后DP，用f[i][j]表示考虑A的前i个字符，在自动机上走到节点j至少需要几步。答案是f[n][null]
转移就是看节点j有没有A[i + 1]的出边，更新。
好的，接下来上我的SB解法......
第一问，广义后缀自动机裸题。
第二问，我们只需要找出A中的一个子串，它向前/后添加一个字符时在B中无法继续匹配即可。
对A建后缀自动机。
由于这样后缀自动机一个节点的多个子串是逐渐在前面添加字符，所以考虑从后往前找子串，在B中也从后往前匹配。
每个节点有一个posA表示该节点代表的的串的结尾在A中的位置，还有一个pos表示该节点代表的最长串在在B中从后向前贪心匹配到的最右距离。
在fail树上DFS。每个点继承它父亲的pos并一个一个贪心匹配直到这个点代表的最长串完成匹配。如果失配了就更新答案。否则就记录pos，向下DFS。
第三问，首先可以得知，如果A中的每一个字符都在B中出现过，那么符合条件的A一定是B的一个子串加上一个B中没有的转移。
于是建出B的后缀自动机。
我们用pos[x]表示节点x所表示的最短子串在A中从前往后贪心匹配到的最短距离。为什么是最短呢？因为我们要越短越好 + 越靠左越好。因为这个节点的每个子串加上一个不存在的转移都会合法，所以短比长优。而靠左的更可能在A中找到B不存在的转移。
而不存在一个非最短子串的最靠左距离会左于最短子串。
于是我们分析了一大通之后发现，只要按照拓扑序更新pos，取最小值就行了。
在每个节点的pos[x]+1开始向右扫A，如果没有转移就更新答案。否则更新下一个节点的pos。
第四问实在是想不出来了，就跑去看题解，学习了一波序列自动机，用了正解写的。
1 #include2 #include 3 #include 4 #include 5 6 const int N = 8010; 7 8 struct Edge { 9 int nex, v; 10 }edge[N << 1]; int top; 11 12 int tr[N * 2][26], fail[N], len[N], tot, cnt[N], bin[N], topo[N], last; 13 int e[N], n, m; 14 char A[N], B[N]; 15 16 inline void add(int x, int y) { 17 top++; 18 edge[top].v = y; 19 edge[top].nex = e[x]; 20 e[x] = top; 21 return; 22 } 23 24 inline void insert(char c) { 25 int f = c - 'a'; 26 int p = last, np = ++tot; 27 last = np; 28 len[np] = len[p] + 1; 29 while(p && !tr[p][f]) { 30 tr[p][f] = np; 31 p = fail[p]; 32 } 33 if(!p) { 34 fail[np] = 1; 35 } 36 else { 37 int Q = tr[p][f]; 38 if(len[Q] == len[p] + 1) { 39 fail[np] = Q; 40 } 41 else { 42 int nQ = ++tot; 43 len[nQ] = len[p] + 1; 44 fail[nQ] = fail[Q]; 45 fail[Q] = fail[np] = nQ; 46 memcpy(tr[nQ], tr[Q], sizeof(tr[Q])); 47 while(tr[p][f] == Q) { 48 tr[p][f] = nQ; 49 p = fail[p]; 50 } 51 } 52 } 53 return; 54 } 55 56 inline void clear() { 57 memset(tr, 0, sizeof(tr)); 58 memset(fail, 0, sizeof(fail)); 59 memset(e, 0, sizeof(e)); 60 memset(len, 0, sizeof(len)); 61 memset(bin, 0, sizeof(bin)); 62 memset(topo, 0, sizeof(topo)); 63 memset(cnt, 0, sizeof(cnt)); 64 last = tot = top = 0; 65 return; 66 } 67 68 namespace t1 { 69 bool vis[N]; 70 inline int split(int p, int f) { 71 int Q = tr[p][f], nQ = ++tot; 72 len[nQ] = len[p] + 1; 73 fail[nQ] = fail[Q]; 74 fail[Q] = nQ; 75 memcpy(tr[nQ], tr[Q], sizeof(tr[Q])); 76 while(tr[p][f] == Q) { 77 tr[p][f] = nQ; 78 p = fail[p]; 79 } 80 return nQ; 81 } 82 inline int insert(char c, int p) { 83 int f = c - 'a'; 84 if(tr[p][f]) { 85 int Q = tr[p][f]; 86 if(len[Q] == len[p] + 1) { 87 return Q; 88 } 89 return split(p, f); 90 } 91 int np = ++tot; 92 len[np] = len[p] + 1; 93 while(p && !tr[p][f]) { 94 tr[p][f] = np; 95 p = fail[p]; 96 } 97 if(!p) { 98 fail[np] = 1; 99 }100 else {101 int Q = tr[p][f];102 if(len[Q] == len[p] + 1) {103 fail[np] = Q;104 }105 else {106 fail[np] = split(p, f);107 }108 }109 return np;110 }111 void DFS(int x) {112 if(vis[x] || !x) {113 return;114 }115 vis[x] = 1;116 DFS(fail[x]);117 return;118 }119 inline void solve() {120 int last = 1;121 tot = 1;122 for(int i = 0; i < n; i++) {123 last = insert(A[i], last);124 }125 last = 1;126 for(int i = 0; i < m; i++) {127 last = insert(B[i], last);128 }129 // SAM over130 int p = 1;131 for(int i = 0; i < m; i++) {132 p = tr[p][B[i] - 'a'];133 DFS(p);134 }135 int ans = n + m;136 for(int i = 2; i <= tot; i++) {137 if(!vis[i]) {138 ans = std::min(ans, len[fail[i]] + 1);139 }140 }141 printf("%d\n", (ans != n + m) ? ans : -1);142 return;143 }144 }145 146 namespace t2 {147 // pos[i] Node i's last position in B148 int pos[N], posA[N], ans;149 std::queue Q;150 void DFS(int x) {151 //printf("x = %d posA[x] = %d \n", x, posA[x]);152 int p = pos[fail[x]] - 1;153 for(int i = posA[x] - len[fail[x]]; i >= posA[x] - len[x] + 1; i--) {154 //printf(" > i = %d \n", i);155 while(p >= 0 && B[p] != A[i]) {156 //printf(" > > p = %d \n", p);157 p--;158 }159 //printf(" > > p = %d \n", p);160 if(p < 0) {161 ans = std::min(ans, posA[x] - i + 1);162 return;163 }164 else {165 pos[x] = p;166 p--;167 }168 }169 for(int i = e[x]; i; i = edge[i].nex) {170 int y = edge[i].v;171 DFS(y);172 }173 return;174 }175 inline void solve() {176 clear();177 last = tot = 1;178 for(int i = 0; i < n; i++) {179 int t = tot;180 insert(A[i]);181 for(int j = t + 1; j <= tot; j++) {182 posA[j] = i;183 }184 }185 ans = n + m;186 for(int i = 2; i <= tot; i++) {187 add(fail[i], i);188 //printf("add %d %d \n", fail[i], i);189 }190 pos[1] = m;191 DFS(1);192 printf("%d\n", ans != n + m ? ans : -1);193 return;194 }195 }196 197 namespace t3 {198 int pos[N], ans;199 inline void solve() {200 for(int i = 0; i < m; i++) {201 bin[B[i]]++;202 }203 for(int i = 0; i < n; i++) {204 if(!bin[A[i]]) {205 printf("1\n");206 return;207 }208 }209 clear();210 tot = last = 1;211 for(int i = 0; i < m; i++) {212 insert(B[i]);213 }214 for(int i = 1; i <= tot; i++) {215 bin[len[i]]++;216 }217 for(int i = 1; i <= tot; i++) {218 bin[i] += bin[i - 1];219 }220 for(int i = 1; i <= tot; i++) {221 topo[bin[len[i]]--] = i;222 }223 //224 memset(pos, 0x3f, sizeof(pos));225 ans = n + m;226 pos[1] = -1;227 for(int a = 1; a <= tot; a++) {228 int x = topo[a];229 for(int i = pos[x] + 1; i < n; i++) {230 int f = A[i] - 'a';231 if(!tr[x][f]) {232 ans = std::min(ans, len[fail[x]] + 2);233 }234 else {235 pos[tr[x][f]] = std::min(pos[tr[x][f]], i);236 }237 }238 }239 printf("%d\n", ans != n + m ? ans : -1);240 return;241 }242 }243 244 namespace t4 {245 int nex[N][26], last[26], f[2010][2010];246 inline void exmin(int &a, int b) {247 a > b ? a = b : 0;248 return;249 }250 inline void solve() {251 clear();252 memset(f, 0x3f, sizeof(f));253 for(int i = 0; i < 26; i++) {254 last[i] = m + 2;255 }256 for(int i = m - 1; i >= 0; i--) {257 for(int j = 0; j < 26; j++) {258 nex[i + 2][j] = last[j];259 }260 last[B[i] - 'a'] = i + 2;261 }262 for(int j = 0; j < 26; j++) {263 nex[1][j] = last[j];264 }265 f[0][1] = 0;266 for(int i = 0; i < n; i++) {267 for(int j = 1; j <= m + 2; j++) {268 exmin(f[i + 1][j], f[i][j]);269 int k = A[i] - 'a';270 //printf("i %d j %d nex[j][k] %d \n", i, j, nex[j][k]);271 // tr[j][f]272 if(!nex[j][k]) {273 continue;274 }275 exmin(f[i + 1][nex[j][k]], f[i][j] + 1);276 //printf("f %d %d -> f %d %d : %d \n", i, j, i + 1, nex[j][k], f[i][j] + 1);277 }278 }279 printf("%d\n", f[n][m + 2] == f[n][m + 3] ? -1 : f[n][m + 2]);280 return;281 }282 }283 284 int main() {285 scanf("%s%s", A, B);286 n = strlen(A);287 m = strlen(B);288 t1::solve();289 t2::solve();290 t3::solve();291 t4::solve();292 293 return 0;294 }
附：序列自动机。
对于长为n的序列，序列自动机有n + 1个节点，分别表示这n个位置和起点。每个节点都有字符集个转移边，指向该字符在它之后第一次出现的位置。fail指针指向上一个它出现的位置。
能够识别所有的子序列。