Description
【题目描述】
众所周知,一个基因可被视为是一种序列,包括了4种核苷酸,可由四个字母表示,A,C、G、T。
一个工程师在进行遗传基因项目的研究,他有这样一项工作:
例如有一个基因“ATCC”。工程师想重新整理它变成“CTCA”。
他能使用两种操作:
(1)交换基因的前两个字母;
(2)移动基因的第一个字母到最后。例如“ATCC”利用操作2可以变成“TCCA”,利用操作1可以变成“CTCA”。
你的任务是写一个程序找出将第一种基因变换成第二种情况的最少操作次数。
【输入格式】
多组数据。每组数据第一行为正整数N表示基因的长度(1≤N≤12)。第二行为原基因序列,第三行为目标基因序列。对于每一种字母,这两个基因具有相同的数目。
最后一行为数字0,表示输入结束。
【输出格式】
每组数据输出一行,输出最少操作步骤。
【样例输入】
4
ATCC
CTCA
4
ATCG
GCTA
4
ATCG
TAGC
0
【样例输出】
2
4
6