算法: 求最长的回文

来源:转载

还是从原来的博客转一两篇有意义的过来吧!

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

输入: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 < 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; } }
上面的start[i]代表当前回文数的开始下表,len[i]是当前回文数的长度,就比如说123321吧,当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]);
} 自己发明的算法,文本上没有什么可以参考的蓝本,写得不好请见谅。


分享给朋友:
您可能感兴趣的文章:
随机阅读: