CSP-S 2020 初赛 阅读程序第3题 双向搜索

// 程序含义：给出原字符串和目标字符串
// 通过旋转[0,m] [m,len-1]区间，判断可否从原字符串得到目标字符串
// 算法：双向搜索
// 基本思路是从起点和重点同时开始广搜，如果发现搜索的两端相遇了
// 就认为是获得了可行解

#include <iostream>
#include <queue>

using namespace std;

const int maxl = 20000000;

// 手动实现哈希
class Map {
    struct item {
        string key;   // 字符串
        int value;    // 记录步数
    } d[maxl];        

    int cnt;

    public:
    int find(string x) {
        for (int i = 0; i < cnt; ++i)     // 遍历一遍，看是否存在字符串x，存在就返回value
            if (d[i].key == x)
                return d[i].value;        
        return -1;
    }

    static int end() { return -1; }  // 这是一个障眼法，就是返回-1

    void insert(string k, int v) {   // 存入数组，就是插入map
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];    // s[0]给st0原字符串用，s[1]给st1目标字符串用

// 手动实现queue
class Queue {
    string q[maxl];

    int head, tail;

    public:
    void pop() { ++head; }                    // 几个队列的常规操作
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x;  }
} q[2];    // q[0]给st0用，q[1]给st1用

string st0, st1;
int m;

string LtoR(string s, int L, int R) {        // LtoR，向左循环
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}

string RtoL(string s, int L, int R) {       // RtoL，向右循环
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}

bool check(string st , int p, int step) {
    if (s[p].find(st) != s[p].end())          // 字符串st存在，返回value, 不是-1，return false
        return false;

    ++step;                                   // 下面就是st不存在，要插入map，入队
    if (s[p ^ 1].find(st) == s[p].end()) {    // 判断一下，从另一头搜索的过程中，是否出现过
        s[p].insert(st, step);                // 另一头也没碰到过这个字符串，就插入，入队
        q[p].push(st);
        return false;                         // return false
    }

    cout << s[p ^ 1].find(st) + step << endl; // 在另一头搜索碰到过st，那好，结束战斗
    return true;                              // 输出value+step，return true
}

int main() {
    cin >> st0 >> st1;                        // st0原字符串，st1目标字符串

    int len = st0.length();
    if (len != st1.length()) {                // 两个字符串长度不等，怎么旋转都不可能实现
        cout << -1 << endl;
        return 0;
    }

    if (st0 == st1) {                         // 如果两个字符串一样，不用干，直接完活
        cout << 0 << endl;
        return 0;
    }

    cin >> m;                                 // 这个m，是规定旋转的规矩，[0,m] [m,len-1]这样旋转
    s[0].insert(st0, 0); s[1].insert(st1, 0); // st0插入s[0], st1插入s[1]
    q[0].push(st0); q[1].push(st1);           // st0入队q[0], st1入队q[1]

    // 这个地方，一行看，会舒服很多
    // q[0]和q[1]没有全空，就继续    
    // p ^= 1 就是 0 1 来回倒腾，代表 从原字符串开始的搜索 从目标字符串开始的搜索 
    for (int p = 0; !(q[0].empty() && q[1].empty());p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);

        if ((p == 0 &&
            (check(LtoR(st, m, len - 1), p, step) ||check(RtoL(st, 0, m), p, step)))
            // p==0代表从原字符串搜索的方向
            // [m,len-1]向左旋转, [0,m]向右旋转

            ||

            (p == 1 &&
            (check(LtoR(st, 0, m), p, step) || check(RtoL(st, m, len - 1), p, step))))
            // p==1代表从目标字符串搜索的方向
            // [0,m]向左旋转, [m,len-1]向右旋转

            return 0;       // 只有两个方向的搜索有一个搜到碰上了，check函数return了true，就结束
    }

    cout << -1 << endl;  // 这个代表，两头搜索，都没搜到，输出-1，表示无法实现

    return 0;
}

// 测试数据的解释
// 从原字符串出发，我们看一下旋转过程
// abc
// [0,1]向左旋转   [1,2]向右旋转
// acb                   bac
// cab                   bca 得到答案

// 原字符串和目标字符串相等，输出0

// m = 0, 旋转区间[0,0]向左旋转, [0,100]向右旋转
// m = 100, 旋转区间[0,100]向左旋转, [100,100]向右旋转
// 这会导致不同的旋转结果

// O(n! * n!)

//  主要的时间复杂度，是在
    for (int i = 0; i < cnt; ++i)     // 遍历一遍，看是否存在字符串x，存在就返回value
            if (d[i].key == x)
                return d[i].value;     
// cnt从1开始递增
// 从原字符串这端的搜索1*2*3*4*5....
// 从目标字符串这端的搜索1*2*3*4*5....

// abc
// cba
// 不可能旋转实现

// 方法一：打表找规律
// 方法二：神看出来了通项是 n^2 / 2 - 4

// 举例，n = 5奇数, m = 2偶数
// st0 12345
// st1 32145

//  012  234
// [123][345]
// [321][145]
// 这样旋转，123 是不可能旋转得到 321的，这样，就会输出-1

// 举例，n = 4偶数, m = 1奇数
// st0 1234
// st1 2134

//  01  123
// [12][234]
// [21][134]
// 是可以旋转得到的

// 还有一个思路，如下 
// https://blog.csdn.net/fengqiyuka/article/details/109084191

总结：

CSP-S 2020初赛的题解很少，往上就找到两篇质量高的题解

「CSP-S 2020」初赛解析

2020CSP-S初赛小结_fengqiyuka的博客-CSDN博客

对于这道《双向搜索》，经过分析，我总结出来这篇，希望提供给大家帮助。文章中有不严谨的地方，还请多指教。