From: http://zhedahht.blog.163.com/。整理出版物请和作者联系。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4.
For example, input the string "google", the maximum length of symmetrical substring is "goog", then output 4.
要判断一个字符串是不是对称的，不是一件很难的事情。我们可以先得到字符串首尾两个字符，判断是不是相等。如果不相等，那该字符串肯定不是对称的。否则我们接着判断里面的两个字符是不是相等，以此类推。基于这个思路，我们不难写出如下代码：
It is not very difficult to determine whether or not a string is symmetrical. We can compare the symbols from the begin and end of the string, to see whether they are equal. If they are not equal, this string is not symmetrical. If they are equal, we can continue to compare the inner symbols. Based upon this idea, the code can be described as follows:
要判断一个字符串pString是不是对称的，我们只需要调用IsSymmetrical(pString, &pString[strlen(pString) – 1])就可以了。
To determine whether a string pString is symmetrical, we
现在我们试着来得到对称子字符串的最大长度。最直观的做法就是得到输入字符串的所有子字符串，并逐个判断是不是对称的。如果一个子字符串是对称的，我们就得到它的长度。这样经过比较，就能得到最长的对称子字符串的长度了。于是，我们可以写出如下代码：
我们来分析一下上述方法的时间效率。由于我们需要两重while循环，每重循环需要O（n）的时间。另外，我们在循环中调用了IsSymmetrical，每次调用也需要O（n）的时间。因此整个函数的时间效率是O（n3）。
There are two "while' loop in the code. In every loop, we should use IsSymetrical funtion, which also needs O(n) time. The total time performance is O(n^3).
通常O（n3）不会是一个高效的算法。如果我们仔细分析上述方法的比较过程，我们就能发现其中有很多重复的比较。假设我们需要判断一个子字符串具有aAa的形式（A是aAa的子字符串，可能含有多个字符）。我们先把pFirst指向最前面的字符a，把pLast指向最后面的字符a，由于两个字符相同，我们在IsSymtical函数内部向后移动pFirst，向前移动pLast，以判断A是不是对称的。接下来若干步骤之后，由于A也是输入字符串的一个子字符串，我们需要再一次
判断它是不是对称的。也就是说，我们重复多次地在判断A是不是对称的。
Usually, O(n^3) is not an effective algorithm. If we carefully analyze the process of the comparison, many repeated comparison can be found. For example, if we determine the symmetry of the substring aAa, we should compare aA firstly, and then compare aAa. However, after that, we will continue to compare Aa and a, which is not necessary to compare them again.
造成上述重复比较的根源在于IsSymmetrical的比较是从外向里进行的。在判断aAa是不是对称的时候，我们不知道A是不是对称的，因此需要花费O（n）的时间来判断。下次我们判断A是不是对称的时候，我们仍然需要O（n）的时间。
The main reason leading to the repeated comparison is that we compare the string from the outer to the inner. When checking the symmetry of aAa, we don't know whether A is symmetrical. It still costs O(n) to determine it.
如果我们换一种思路，我们从里向外来判断。也就是我们先判断子字符串A是不是对称的。如果A不是对称的，那么向该子字符串两端各延长一个字符得到的字符串肯定不是对称的。如果A对称，那么我们只需要判断A两端延长的一个字符是不是相等的，如果相等，则延长后的字符串是对称的。因此在知道A是否对称之后，只需要O（1）的时间就能知道aAa是不是对称的。
we can change our mine to determine the symmetry from the inner to the outer. We can check whether the substring A is symmetrical. If not, the extension of this substring is definitively not symmetrical. If A is symmetrical, the only thing we can do is to check the extension of A is symmetrical. Thus, the time performance of o(1) is needed to check wheterh aAa is symmetrical. The code is as follows:
我们可以根据从里向外比较的思路写出如下代码：
由于子字符串的长度可能是奇数也可能是偶数。长度是奇数的字符串是从只有一个字符的中心向两端延长出来，而长度为偶数的字符串是从一个有两个字符的中心向两端延长出来。因此我们的代码要把这种情况都考虑进去。
在上述代码中，我们从字符串的每个字符串两端开始延长，如果当前的子字符串是对称的，再判断延长之后的字符串是不是对称的。由于总共有O（n）个字符，每个字符可能延长O（n）次，每次延长时只需要O（1）就能判断出是不是对称的，因此整个函数的时间效率是O（n2）。
没有评论:
发表评论