P4112 [HEOI2015]最短不公共子串

题目描述

在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。

一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。

一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。

下面，给两个小写字母串A，B，请你计算：

(1) A的一个最短的子串，它不是B的子串

(2) A的一个最短的子串，它不是B的子序列

(3) A的一个最短的子序列，它不是B的子串

(4) A的一个最短的子序列，它不是B的子序列

输入输出格式

输入格式：

有两行，每行一个小写字母组成的字符串，分别代表A和B。

输出格式：

输出4行，每行一个整数，表示以上4个问题的答案的长度。如果没有符合要求的答案，输出-1

说明

对于20%的数据，A和B的长度都不超过20

对于50%的数据，A和B的长度都不超过500

对于100%的数据，A和B的长度都不超过2000

---

四合一还行。

问题1

建立B的后缀自动机

枚举A的开头，然后在B上从S向后跑，失配了更新答案

问题2

建立B的序列自动机

然后一样的

问题3

在B的后缀自动机上跑DP（这样才能处理A的子序列）

具体的\(dp_i\)表示这个点可以匹配上的最短长度

从头开始枚举每个点更新。

问题4

在B的序列自动机上跑，其他和三一样

数据太水，3,4的dp01背包写成完全背包也可以过...

我3的dp写的是假的，懒得改了..

---

Code:

#include 
    
     #include 
     
      const int N=4010;const int inf=0x3f3f3f3f;char s1[N],s2[N];int n,dp[N];int min(int x,int y){return x
     
    

---

2019.1.7