LittleElephantAndString

作者：袁伟强

关键词：字符串

题目简述

给两个长度相等的字符串$A,B$，每次可以在$A$中任选一个字符并移到串的开头。求将$A$变成$B$的最小操作次数（无解返回$-1$）。

$1\leq |A|=|B|=N\leq 50$

$A,B$只包含大写字母

算法

我们先来看看什么时候无解。如果存在一种字母，它在$A$和$B$中出现的次数不同，那显然是无解的。如果每种字母在$A$和$B$中出现的次数都相同，那么可以将$A$中的字母和$B$中的字母建立起一一对应关系，从后往前枚举$B$中的每个字母，将$A$中与之对应的字母移到$A$的开头，这样就能将$A$变成$B$了。至此，我们证明了有解的充要条件是每种字母在$A$和$B$中出现的次数都相同。

下面所要求的就是最优解了。注意到，移动一个字母并不会改变其他字母的相对顺序，也就是说，对于一个字母，只有最后一次移动是有效的，所以，在最优解中，每个字母最多只被移动了一次。下面，我们来看看那些字母可以不用被移动。首先，不被移动的字母一定是B的后缀。而移动其他字母，并不会改变这些字母的相对顺序，因此，$B$的这个后缀必须为$A$的子序列。而如果知道$B$的某个后缀是$A$的子序列，仿照之前证明有解的充分条件，发现只要移动其他字母，必能将$A$变成$B$。

至此，问题已经转化成求$B$的最长后缀，使得其为$A$的子序列。这个问题十分容易，我们只需从后往前枚举$B$的每个字母，同时在$A$中维护一个指针从后往前扫过去，时间复杂度$O(N)$ 。