首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#13193

字母游戏 一个简单的字母游戏是这样进行的:游戏开始时,我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母,只是顺序不同。换句话说,将 S 中的…

字母游戏

一个简单的字母游戏是这样进行的:游戏开始时,我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母,只是顺序不同。换句话说,将 S 中的字母重排顺序就可以得到 T。游戏的每一步,我们可以将 S 中的任一字母移动到串头或串尾,问将 S 变换成 T 至少需要多少步?

时间限制:6000

内存限制:65536

输入

输入分两行,先后给出字母串 S 和 T。如题面所描述的,两者包含同样的小写英文字母,只是顺序不同。每个字母串的长度不超过 1000。

输出

在一行中输出将 S 变换成 T 至少需要的步骤数。


样例输入

iononmrogdg
goodmorning

样例输出

8

提示

样例解释:

1、 从 iononmrogdg 开始;

2、 将最后一个 g 移动到串头: giononmrogd;

3、 将 m 移动到串尾: giononrogdm;

4、 将第一个 o 移动到串尾: ginonrogdmo;

5、 将 r 移动到串尾: ginonogdmor;

6、 将第一个 n 移动到串尾: gionogdmorn;

7、 将 i 移动到串尾: gonogdmorni;

8、 将第一个 n 移动到串尾: googdmornin;

9、 将第二个 g 移动到串尾: goodmorning。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>参考代码</p><pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int main() {     string s, t;     cin &gt;&gt; s &gt;&gt; t;     int n = s.size();          unordered_map&lt;char, vector&lt;int&gt;&gt; pos_map;     for (int i = 0; i &lt; n; ++i) {         pos_map[s[i]].push_back(i);     }          int max_len = 0;     for (int i = 0; i &lt; n; ++i) {         int current_pos = -1;         int count = 0;         for (int j = i; j &lt; n; ++j) {             char c = t[j];             if (pos_map.find(c) == pos_map.end()) {                 break;             }             vector&lt;int&gt;&amp; v = pos_map[c];             auto it = upper_bound(v.begin(), v.end(), current_pos);             if (it == v.end()) {                 break;             }             current_pos = *it;             count++;         }         if (count &gt; max_len) {             max_len = count;         }     }          cout &lt;&lt; n - max_len &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。