Chinaunix首页 | 论坛 | 博客
  • 博客访问: 65029
  • 博文数量: 115
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 10
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-08 19:09
文章分类
文章存档

2015年(115)

我的朋友

分类: C/C++

2015-08-06 16:49:27

题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串“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,无法处理对称长度是奇数的情况
 

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. int symlen(const char* src){
  5.     if(src == NULL) return -1;
  6.     int len = strlen(src);
  7.     int last = 0;
  8.     int max = last;
  9.     int cur;
  10.     int i;
  11.     for(i = 0; i<len; i++){
  12.                 if(last>1 && src[i] == src[i-last-1]){
  13.             cur = last +2;
  14.         }
  15.         else if(src[i] == src[i-2]){
  16.             cur = 3;
  17.         }
  18.         else if(src[i] == src[i-1])
  19.             cur = 2;
  20.         else
  21.             cur = 1;
  22.         max = max>cur?max:cur;
  23.                 printf("%d %d\n",i, cur);
  24.         last = cur;
  25.     }
  26.     return max;
  27.     
  28. }

  29. int main(){
  30.     char * str = "teetgooogle";
  31.     int ret = symlen(str);
  32.     printf("%d \n", ret);
  33. }

阅读(189) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~