喜串

4月5日 · 2018年
jxtxzzw · ·

喜串的定义:字符串 a 与字符串 b 互为喜串需满足以下两个条件之一:

ab 相同。
a 分成 a1a2 两个等长串,b 分成 b1b2 两个等长串,其子串需满足以下两个条件之一:
a1b1 互为喜串且 a2b2 互为喜串。
a1b2 互为喜串且 a2b1 互为喜串。

Input
输入两行字符串(仅包含小写字母)
长度不超过 $$2^{18}$$

Output
输出一行 YesNo

OJ链接
https://acm.ecnu.edu.cn/contest/58/problem/A/

首先可以明确,如果a和b长度不等,就一定不会是喜串

又因为是要分成等长的两部分,所以显然如果a和b的长度为奇数,那么当且仅当a和b相等的时候才是喜串,否则不可能继续分下去了

除此而外的情况,首先判断a和b是不是相等,如果不相等,就利用定义,二分递归地逐层检查

递归的边界是n=1,这时不再二分,而检查是不是相等

但是当n=1时,由于上面的分析,长度为奇数,如果始终保证判断相等性在二分之前,那么自然就成了递归边界

首先给出第一个版本的代码

private static boolean isPairs(String a, String b) {
    if (a == null || b == null)
        return false;
    if (a.length() != b.length())
        return false;
    int length = a.length();
    if (length % 2 == 0) {
        if (a.equals(b))
            return true;
        else {
            if (a.equals(b))
                return true;
            String a1 = a.substring(0, length / 2);
            String a2 = a.substring(length / 2, length);
            String b1 = b.substring(0, length / 2);
            String b2 = b.substring(length / 2, length);
            return ((isPairs(a1, b1) && isPairs(a2, b2)) || (isPairs(a1, b2) && isPairs(a2, b1)));
        }
    } else {
        return a.equals(b);
    }
}

可以用更优化的算法,也就是说,上面的这个

((isPairs(a1, b1) && isPairs(a2, b2)) || (isPairs(a1, b2) && isPairs(a2, b1)))

不用全部运行,最多运行3个就行了

所以下面我逐步给出优化的算法

如果把字符串分成a1a2b1b2

首先判断a1b1是不是互为喜串,记为f1

然后判断a1b2是不是互为喜串,记为f2

看定义:

  • a1b1互为喜串且a2b2互为喜串

  • a1b2互为喜串且a2b1互为喜串

  1. 如果f1falsef2false

那么就不用比较了

一定不可能是互为喜串

因为喜串的定义中a1b1互为喜串、a1b2互为喜串都不满足了

  1. 如果f1falsef2true

那么a1b1互为喜串且a2b2互为喜串已经不可能满足

只要看a1b2互为喜串且a2b1互为喜串是不是满足

所以只要比较a2b1是不是互为喜串

  1. 如果f1truef2false

同样的,所以只要比a2b2是不是互为喜串

  1. 如果f1truef2true

那么接下来只要任意比较一次a2b2

或者,a2b1

不妨假设比较的是a2b1

如果这时候是互为喜串,那么满足定义之一,ab就是互为喜串

如果这时候不是互为喜串

下面证明a2b2一定不可能互为喜串

反证法
$$
\begin{align}
假设a2与b2互为喜串\\
那么由于a1与b2互为喜串\\
由于喜串的定义具有传递性(下详)\\
a1与a2互为喜串\\
又a1与b1互为喜串\\
所以a2与b1互为喜串\\
矛盾
\end{align}
$$
所以程序可以修改为

bool isPairs(string a, string b) {
    if (a.length() != b.length())
        return false;
    int length = a.length();
    if (length % 2 == 0) {
        if (a.compare(b) == 0)
            return true;
        else {
            if (a.compare(b) == 0)
                return true;
            string a1 = a.substr(0, length / 2);
            string b1 = b.substr(0, length / 2);
            string b2 = b.substr(length / 2, length / 2);
            bool f1 = isPairs(a1, b1);
            bool f2 = isPairs(a1, b2);
            if (f1 == false && f2 == false) return false;
            string a2 = a.substr(length / 2, length / 2);
            if (f1 == true && f2 == false) return isPairs(a2, b2);
            if (f1 == true && f2 == true) return isPairs(a2, b2);
            return isPairs(a2, b1);
            }
    } else {
        return (a.compare(b) == 0);
    }
}

上面的证明中提到了传递性,下面简要说说证明思路,证明过程从略
$$
\begin{align*}
&欲证:若a和b互为喜串,b和c互为喜串,则a和c互为喜串\\
\\
&数学归纳法\\
\\
&首先明确,a和b和c的长度一定一样\\
&若长度为1,则a和b互为喜串当且仅当a=b,b和c互为喜串当且仅当b=c,于是有a=b=c\\
&所以a和c互为喜串\\
&若长度为2,则满足以下任一情况都认为互为喜串\\
&第1,a=b,b=c,同样地有a=b=c\\
&第2,a[0]和b[0]互为喜串且a[1]和b[1]互为喜串\\
&第3,a[1]和b[0]互为喜串且a[0]和b[1]互为喜串\\
&对于后面两种情况,递归地,可以证明a、b、c两两互为喜串\\
&若长度为4,同样归纳\\
&……\\
&于是,所有长度为2^k的串,都可以类似证明\\
&然后考虑长度为3、6、12……\\
&考虑长度为5、10、20……\\
&对于所有的长度为(2k+1)的串,都可以用归纳假设,递推地,证明后面的结论成立\\
&而所有(2k+1)的串,因为不可能进一步分解成等分的串,所以只可能是a=b=c这一种情况\\
\end{align*}
$$
但是

每次都要复制string的值到substring

内存和时间的开销也是非常大的

于是考虑不要每次复制出substring

而是每次给定比较的起始位置和长度

改成

bool isPairs(char *a, int lengthA, char *b, int lengthB) {
    if (lengthA != lengthB)
        return false;
    int length = lengthA;
    if (length % 2 == 0) {
        if (strncmp(a, b, length) == 0)
            return true;
        else {
            if (strncmp(a, b, length) == 0)
                return true;
            bool f1 = isPairs(a, length / 2, b, length / 2);
            bool f2 = isPairs(a, length / 2, b + length / 2, length / 2);
            if (f1 == false && f2 == false) return false;
            if (f1 == true && f2 == false) return isPairs(a + length / 2, length / 2, b + length / 2, length / 2);
            if (f1 == true && f2 == true) return isPairs(a + length / 2, length / 2, b + length / 2, length / 2);
            return isPairs(a + length / 2, length / 2, b, length / 2);
        }
    } else {
        return (strncmp(a, b, length) == 0);
    }
}

以上代码测试通过

其实还有更快的方法,如果a和b互为喜串,那么与a互为喜串且字典序最小的字符串x,和与b互为喜串且字典序最小的字符串y应该是完全一样的,怎么求字典序最小的喜串,可以留作思考

0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定