微软面试100题(73):字符串中对称字符串的最大长度

题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

最近DP的题做了好多了。。

这是个情况分的比较多的dp题。

设输入为input,长度为len

1.设f(n)为到 input[i]为止，且包含input[i]的对称子串的最大长度。

2.那么计算f(n+1)，对于新读到的字符input[n+1]:

   a.如果input[n+1] == input[ n- f(n) -1]。 就是说，新增的字符，如果和n的时候的最长对称字串的前一个相同， 那么对称子串可以前后延长一位。

            有 f(n+1) = f(n)+2

   b.如果input[n+1] == input[n-1].即aba,说明这个对称长度是3，有

             f(n+1) = 3

   c.如不相同，那么如果input[n+1]==input[n]。就是说，新增字符和它的钱一个相同。

             有f(n+1) = 2

   d.如果两个条件都不满足，说明如果包含它，完全和前面的无法对称。

             有f(n+1) = 1

根据以上分析得出的f(n)和f(n-1)的关系，有代码如下。其复杂度为O(n).

 

Update:

修正原来漏掉的情况b,并修正代码。若无情况b,无法处理对称长度是奇数的情况

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int symlen(const char* src){
    if(src == NULL) return -1;
    int len = strlen(src);
    int last = 0;
    int max = last;
    int cur;
    int i;
    for(i = 0; i<len; i++){
                if(last>1 && src[i] == src[i-last-1]){
            cur = last +2;
        }
        else if(src[i] == src[i-2]){
            cur = 3;
        }
        else if(src[i] == src[i-1])
            cur = 2;
        else
            cur = 1;
        max = max>cur?max:cur;
                printf("%d %d\n",i, cur);
        last = cur;
    }
    return max;

}

int main(){
    char * str = "teetgooogle";
    int ret = symlen(str);
    printf("%d \n", ret);
}