[算法讨论] 平方串

[Zhao Quan]

这是我被面到的一道面试题，当时写出的算法未得到肯定的评价。

觉得有点难度故发上来和大家讨论下。

平方串

是含有偶数个字符的串，且前半部分与后半部分完全相同。

如：abcabc 是一个平方串

空串，不是平方串

现要求

输入任意字符串转换为平方串

通过以下3种method

1, remove a

2, add a

3, change a->b

每使用3个method中的任意一个记1步

求最少步骤次数

[Heiher]

这三个method可以做什么？

[杨帆]

将次问题转化为LCS问题，具体是，

枚举串中的“分隔点”，将其分为两段，再用DP求两段的LCS(最长公共子串)

最坏情况下的复杂度是O(N^3)。。

这个复杂度不知会不会算很高啊。。

2012/3/9 Heiher <ad...@heiher.info>

[杨帆]

补充一下后续步骤，后面就在LCS得到的结果上修改。假设得到了axxxxbxxc和axxbxxxxc两个串，其中a、b、c表示LCS求出之后对应的字符，x表示不对应。则需要的步骤数为4+4=8，就是每次对两个连续不对应的串，取较长的那段加。

2012/3/9 杨帆 <idd...@gmail.com>

[Luo Jiesi]

求出了lcs然后呢？比如两面长分别为m n，lcs长x，怎么求所要的步数

2012/3/9 杨帆 <idd...@gmail.com>

--
luojiesi@zju

@luojiesi

http://www.luojs.com

[Luo Jiesi]

刚刚没看到这一条。。。sorry

2012/3/9 杨帆 <idd...@gmail.com>

[Zhao Quan]

hi 三个method

1 移除任意一个字符，使得串符合“平方串”规则

2 加入任意一个字符，使得串符合“平方串”规则

3 将某一字符以任意一个字符替换，使得串符合“平方串”规则

[Zhao Quan]

谢谢啊，杨帆
也就是说，关键还是在求LCS的问题。

且，这里的LCS，不一定是从串首字母开始的，

且，不一定连续。

请问，您这里提到的DP是指Dynamic Programming，动态规划吗？

谢谢 

[Ray Song]

枚举分割点可以换成二分，这样是O(n^2 log n)

[Xunzhen Quan]

枚举分割点不能二分吧？只能一个一个做过去我觉得……

枚举断点做 LCS 真是个好想法。

2012/3/9 Ray Song <emac...@gmail.com>:

[Rivsen]

他只是想要最少的步骤么，当然是最理想的情况，输入的任意字符串就是一个平方串，这样是用的最少的，为 0 步啊。我想的比较简单，大家不要笑话我啊！

kind regards,

Rivsen

[杨帆]

嗯对Dynamic Programming

2012/3/9 Rivsen <rivse...@gmail.com>

[Qian Hong]

我是路过打酱油的:
以前想过相反的问题, 如何构造"非平方串", 以及用三个字母最长可以构造出多长的"非平方串".
这个问题向Matrix67请教过, 他告诉我以前有人做过:
http://mathworld.wolfram.com/SquarefreeWord.html

感兴趣的朋友可以看看 :)

2012/3/8 Zhao Quan <felix...@gmail.com>:

--
Regards,
Qian Hong

-
Sent from Ubuntu
http://www.ubuntu.com/

[Ray Song]

应该用 edit distance 吧

[Xunzhen Quan]

edit distance 是用来在已知两个串的情况下计算最少编辑步骤吧

2012/3/9 Ray Song <emac...@gmail.com>:

[Yin Wenyan]

前半串为源串，后半串为目标串，即转化为Edit Distance

话说这家公司是干什么的，需要用这样的面试题？

[Xunzhen Quan]

如果不枚举切点的话这个算法是错误的，枚举切点跟上面的 LCS 其实就是一样的了……单纯计算 edit distance 其实就是将 LCS 的结果进行变换吧。

2012/3/9 Yin Wenyan <yiw...@gmail.com>:

[Zhao Quan]

基于EditDistance算法我编写算法如下，语言C#

 

有什么没有疏漏的地方，大家给指点下

 

public class SquareStringOperator
    {
        public static int SquareStringByEditDistance(string s)
        {
            int result = s.Length;
            for (int i = 1; i < s.Length; i++)
            {
                int currCount = AlgorithmCollection.EditDistance(s.Substring(0
, i), s.Substring(i, s.Length - i));
                if (currCount < result)
                    result = currCount;
            }
            return result;
        }
    }

    public class AlgorithmCollection
    {
        public static int EditDistance(string s1, string s2)
        {
            const int _arrayLength = 10;

            int[,] m = new int[_arrayLength, _arrayLength];

            for (int i = 1; i <= s1.Length; i++)
            {
                m[i, 0] = i;
            }

            for (int j = 1; j <= s2.Length; j++)
            {
                m[0, j] = j;
            }

            for (int i = 1; i <= s1.Length; i++)
            {
                for (int j = 1; j <= s2.Length; j++)
                {
                    m[i, j] = Min(m[i - 1, j - 1] + (s1[i - 1] == s2[j - 1] ?
0 : 1),
                        m[i - 1, j] + 1,
                        m[i, j - 1] + 1);
                }
            }

            return m[s1.Length, s2.Length];
        }

        private static int Min(int p, int p_2, int p_3)
        {
            int temp = p_2 < p_3 ? p_2 : p_3;
            return p < temp ? p : temp;
        }
    }

单元测试用例如下：
1 empty
2 ""
3 a
4 aa
5 aac
6 abcabcz

[Zhao Quan]

关于EditDistance的相关资料，在此留档

http://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

[Zhao Quan]

BTW sorry for use C#

Rampup with some spical language is in progress.

[Yin Wenyan]

嗯，对，要枚举切点的。

[zi.Zzway]

从当中开始向两边枚举，到四分之一、四分之三处停止，因为之后的最优解也不会优于N/2

[Yin Wenyan]

啰嗦一些的说法：分隔点在四分之一和四分之三处的最优解为N，而分隔点在二分之一处的最烂解为N，所以不用继续向两边枚举了（注定只会更烂的）。