ccnu 1016ハイブリッド

1016: OOXX
Time Limit: 1 Sec  
Memory Limit: 128 MB
Submit: 12  
Solved: 9
[ Submit][ Status][ Web Board]
Description
OOXXはとても不思议ですよ~话をしてこれは1种の人が人に爱されるので、花が咲く2人の活动を见て、多く室内で、アウトドアは比较的に少ないです......
ええと...上と下は何の関係もありませんが...
ところで、3つの文字列があり、1つ目の文字列はOとXだけで、2つ目と3つ目の文字列は空です.
次の操作があります.
操作1は、Aの一番左の文字を削除し、文字列Bの後ろに接続する
操作2は、Aの一番左の文字を削除し、文字列Cの後ろに接続する
操作3は、Bの一番左の文字を削除し、文字列Aの後ろに接続する
操作4は、Cの一番左の文字を削除し、文字列Aの後ろに接続する
先頭のAの文字列と、所望の文字列Sを与え、文字列Aを上記変換により文字列Sを得るには少なくとも何回の操作が必要かを問う.最後に得られた文字列Sは必ず文字列Aに入れることが要求される.
例えば、先頭文字列がOOXOX、最後文字列がXOXOXOであれば、少なくとも6回変換する必要がある
          A=OOXXOX   B=   C= 
1.A=OXXOX B=O C=操作1
2.A=XXOX B=O C=O操作2
3.A=XOX B=O C=OX操作2
4.A=XOXO B=O C=X操作4
5.A=XOXOX B=O C=操作4
6.A=XOXOXO B=C=操作3
Input
最初の行には、文字列の長さを表す数nが入力されます.2行目に2つの文字列AとSを入力します.各文字列はXとOのみを含み、2つの文字列Xの個数とOの個数が等しいことを保証する.ここでn<=1000.
Output
テストデータごとに出力される数は、最小操作回数を表し、出力ごとに1行を占めます.
Sample Input

6
OOXXOX
XOXOXO
7
OOOXXOO
OOOXXOO

Sample Output

6
0

HINT
この活动はノートで游ぶ五子棋のゲームで、一方がO、一方がXを使うことに惯れているため、別名OOXXと呼ばれています.
Source
 
 
 
解析:常に可能であることを理解するには、2つの一時列があり、2つのアルファベットしかないため、任意の変形を実現することができるので、最長の接頭辞エネルギーと接尾辞を重ね合わせればよいことを理解することができます.