1#include <iostream>2#include <queue>3using namespace std;4 5const int maxl = 20000000;6 7class Map {8    struct item {9        string key; int value;10    } d[maxl];11    int cnt;12  public:13    int find(string x) {14        for (int i = 0; i < cnt; ++i)15            if (d[i].key == x)16                return d[i].value;17        return -1;18    }19    static int end() { return -1; }20    void insert(string k, int v) {21        d[cnt].key = k; d[cnt++].value = v;22    }23} s[2];24 25class Queue {26    string q[maxl];27    int head, tail;28  public:29    void pop() { ++head; }30    string front() { return q[head + 1]; }31    bool empty() { return head == tail; }32    void push(string x) { q[++tail] = x;  }33} q[2];34 35string st0, st1;36int m;37 38string LtoR(string s, int L, int R) {39    string t = s;40    char tmp = t[L];41    for (int i = L; i < R; ++i)42        t[i] = t[i + 1];43    t[R] = tmp;44    return t;45}46 47string RtoL(string s, int L, int R) {48    string t = s;49    char tmp = t[R];50    for (int i = R; i > L; --i)51        t[i] = t[i - 1];52    t[L] = tmp;53    return t;54}55 56bool check(string st , int p, int step) {57    if (s[p].find(st) != s[p].end())58        return false;59    ++step;60    if (s[p ^ 1].find(st) == s[p].end()) {61        s[p].insert(st, step);62        q[p].push(st);63        return false;64    }65    cout << s[p ^ 1].find(st) + step << endl;66    return true;67}68 69int main() {70    cin >> st0 >> st1;71    int len = st0.length();72    if (len != st1.length()) {73        cout << -1 << endl;74        return 0;75    }76    if (st0 == st1) {77        cout << 0 << endl;78        return 0;79    }80    cin >> m;81    s[0].insert(st0, 0); s[1].insert(st1, 0);82    q[0].push(st0); q[1].push(st1);83    for (int p = 0;84            !(q[0].empty() && q[1].empty());85            p ^= 1) {86        string st = q[p].front(); q[p].pop();87        int step = s[p].find(st);88        if ((p == 0 &&89                (check(LtoR(st, m, len - 1), p, step) ||90                 check(RtoL(st, 0, m), p, step)))91                ||92                (p == 1 &&93                 (check(LtoR(st, 0, m), p, step) ||94                  check(RtoL(st, m, len - 1), p, step))))95            return 0;96    }97    cout << -1 << endl;98    return 0;99}100