01 #include <iostream>

02 #include <queue>

03 using namespace std;

04

05 const int max1 = 2000000000;

06

07 class Map (

08 struct item {

09 string key; int value;

10} d[max1];

11int cnt;

12public:

13int find(string x) {

14for (int i = 0; i < cnt; ++i)

15if (d[i].key == x)

16return d[i].value;

17return -1;

18}

19static int end() { return -1; } 

20void insert(string k， int v) {

21d[cnt].key = k; d[cnt++].value = v; 

22}

23} s[2]；

24

25class Queue {

26string q[max1];

27int head, tail;

28public:

29void pop() { ++head; }

30string front() { return q[head + 1]; } 

31bool empty() { return head == tail; } 

32void push(string x) { q[++tail] = x; } 

33} q[2]；

34

35string st0，stl;

36int m;

37

38string LtoR(string s, int L, int R) { 

39string t = s;

40char tmp = t[L];

41for (int i = L; i < R; ++i)

42t[i] = t[i + 1];

43t[R] = tmp;

44return t;

45}

46

47string RtoL(string s， int L，int R) { 

48string t = s;

49char tmp = t[R];

50for (int i = R; i > L; --i)

51t[i] = t[i - 1]；

52t[L] = tmp;

53return t;

54}

55

56bool check(string st， int p，int step) { 

57if (s[p].find(st) != s[p].end()) 

58return false;

59++step;

60if (s[p ^ 1].find(st) == s[p].end()) { 

61s[p].insert(st, step); 

62q[p].push(st);

63return false;

64}

65cout << s[p ^ 1].find(st) + step << end1; 

66return true;

67}

68

69int main() {

70cin >> st0 >> stl;

71int len = st0.length()；

72if (len != stl.length()) { 

73cout << -1 << end1; 

74return 0；

75}

76if (st0 == st1) { 

77cout << 0 << end1; 

78return 0；

79}

80cin >> m;

81s[0].insert(st0, 0); s[1].insert(st1, 0); 

82q[0].push(st0); q[1].push(st1);

83for (int p = 0;

84!(q[0].empty() && q[1].empty());

85p ^=1) {

86string st - q[p].front(); q[p].pop();

87int step = s[p].find(st);

88if ((p == 0 &&

89(check(LtoR(st,m, len - 1), p, step) || 

90check(RtoL(st, 0, m), p, step)))

91|| 

92(p == 1 &&

93(check(LtoR(st,0, m), p, step) || 

94check(RtoL(st, m, len - 1), p, step)))) 

95return 0；

96}

97cout << -1 << end1; 

98return 0；

99}

(1)．

（4分）若两个字符串的长度均为n, 且0<m<n-1,且两个字符串的构 成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列 说法正确的是（）。提示：考虑输入与输出有多少对字符前后顺序不 一样。

A． 若n、m均为奇数，则输出可能小于0	B． 若n、m均为偶数，则输出可能小于 0
C． 若n为奇数、m为偶数，则输出可能小于0	D． 若n为偶数、m为奇敎.则输出可能小于0

(2)．

若两个字符串的长度均为n,则最坏情况下，此程序的时间复杂度为 0（n!）。 （）

A．正确	B．错误

(3)．

（4分）已知当输入为“0123\n3210\n1”时输出为4,当输入为 “012345\n543210\n1”时输出为14,当输入为 “01234567\n76543210\n1”时输出为28,则当输入为 “0123456789ab\nba9876543210\n1” 输出为（）。其中“\n”为换行符。

A． 56	B． 84
C． 102	D． 68

(4)．

（2.5分）若输入的第一个字符串长度由100个不同的字符构成，第二 个字符串是第一个字符串的倒序，输入的m为0，则输岀为（）。

A． 49	B． 50
C． 100	D． -1

(5)．

若输入的两个字符串长度均为101时，则m=0时的输出, m=10O时的 输出是一样的。（）

A．正确	B．错误

(6)．

输出可能为0 （）

A．正确	B．错误