跳至正文

算法: 求最长的回文字符串

  • OI路程

  最近USACO写到了(第三次)1.3.3,这一题我用的是我自己原创的一个算法(可能也有别人想到了,但是对于我来说,确实是我自己独立思考出来的),在此发表一下。
  程序:输入:一行字符串,输出:最长的回文字符的长度以及把它们给输出来。
  如:
    输入:1596156432111234
    输出:6
    432111234

  回文的性质

  首先先把题目撇开,单说回文数的性质,如abcba是一个长度为5的回文数,那它有什么性质呢?
  回文数顾名思义,就是从左念和从右念是相同的,也可以说从左遍历和从右遍历是相同的,这些都是废话。因为它是回文数所以可以同时从左和右开始遍历,各个字符都是相同的。
  其实上面那些性质也没什么用,算是铺垫吧,接下来的才是重点,那怎么样去构成一个回文数呢?就用abcba做例子吧,这个回文数的构成是由单个字符c两边同时放置b,构成的bcb再两边同时放置一个a构成的。

  回文的判定

  那么假设要你判断abcba是不是有两种方法,但是我要说的不是两边同时开始遍历并且判断的方法,再用abcbad做例子吧,用程序判断它是不是一个回文数,我先把过程写出来,然后再把方式写出来。
下面把回文数和回文混用。
  首先下标i=0…5,s[i]代表第i个字符。i从1开始递归,因为第一个字符不存在回文数,i=1时,当前回文长度为1,就是单个字符a。当前回文数长度是我自己定义的名词,就是说以i结尾的回文数的长度。然后i = 2时,当前回文数是单个字符c,长度为1;i=3时,这里需要注意一下了,从这里开始就有一些变化了,当前回文数的长度为3,为bcb,i=4时,当前回文数的长度为5,为abcba,接着i=5,当前回文长度为1,是单个字符d,这样它就不是一个回文数。

  当前回文数长度

  那么求当前回文数的长度(不是标准的语言):
  i = 1
  while(i 3321吧,当i = 3时(123321),start[i] = 2(123321) len[i] = 2;当i = 5时(123321),start[i] = 0(123321),len[i] = 6,也就是说当前回文数的取决于三种情况:
  第一种:start[i – 1]的前面一个字符等于i时,当前回文就是(start[i – 1] – 1) ~ i,长度就是len[i – 1] + 2。
  第二种:s[i – 1]等于s[i],就是说两个相邻的字符相等的话,那么start[i] = i – 1;len[i] = 2。
  第三种:什么都不是,就是单个字符回文,start[i] = i, len[i] = 1。
  其实仔细想想可以把len[]这个数组去掉,因为len[i] = i – start[i] + 1;
  但是,因为这篇文章时根据USACO那题写的,那个题目的s中包含空格和标点符号,但是又把它们记入len[]中,所以这个代码只是一个模式,遇到不同的题目要有不同的待遇,但是这种思想我觉得很重要/神奇,类似于DP但又不是。

  解题

  那么上面的题目就好解了(只给出大致代码):
  i = 1, ans = 0
  while(i < n){
    if(s[start[i – 1] – 1] == s[i]){
      start[i] = start[i – 1] – 1;
      len[i] = len[i – 1] + 2;
    }else if(s[i – 1] == s[i]){
      start[i] = i – 1;
      len[i] = 2;
    }else{
      start[i] = i;
      len[i] = 1;
    }
    if(ans < len[i]){
      ans = len[i];
      k = i;
    }
  }
  printf("%d\n", ans);
  for(i = start[k]; i <= k; i++){
    printf("%c", s[i]);
  }
  自己发明的算法,文本上没有什么可以参考的蓝本,写得不好请见谅。

发表评论

您的电子邮箱地址不会被公开。