背景:
所谓对称子字符串,就是这个子字符串要么是以其中一个词对称:比如 “aba”, “abcba”;要么就完全对称:比如"abba", "abccba"。
问题:
给你一个字符串,找出该字符串中对称的子字符串的最大长度。
思路:
首先,我们用字符数组 char[] array 来保持这个字符串,假设现在已经遍历到第 i 个字符,要找出以该字符为“中心”的最长对称字符串,我们需要用另两个指针分别向前和向后移动,直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况,所以需要写出两种情况下的代码:
1. 第 i 个字符是该对称字符串的真正的中心,也就是说该对称字符串以第 i 个字符对称, 比如: “aba”。代码里用 index 来代表 i.
public static int maxLengthMiddle(char[] array, int index) {
int length = 1; //最长的子字符串长度
int j = 1; //前后移动的指针
while ((array[index - j] == array[index + j]) && (index - j) >= 0 && array.length > (index + j)) {
length += 2;
j++;
}
return length;
}
2. 第 i 个字符串是对称字符串的其中一个中心。比如“abba”。
public static int maxLengthMirror(char[] array, int index) {
int length = 0; //最长的子字符串长度
int j = 0; //前后移动的指针
while ((array[index - j] == array[index + j + 1]) && (index - j) >= 0 && array.length > (index + j + 1)){
length += 2;
j++;
}
return length;
}
有了这样两个函数,我们只需要遍历字符串里所有的字符,就可以找出最大长度的对称子字符串了。
public static int palindrain(char[] array) {
if (array.length == 0) return 0;
int maxLength = 0;
for (int i = 0; i < array.length; i++) {
int tempMaxLength = - 1;
int length1 = maxLengthMiddle(array, i);
int length2 = maxLengthMirror(array, i);
tempMaxLength = (length1 > length2) ? length1 : length2;
if (tempMaxLength > maxLength) {
maxLength = tempMaxLength;
}
}
return maxLength;
}
因为找出以第 i 个字符为“中心”对称字符串复杂度为 O(N),所以整个算法的复杂度为O(N^2)。
另一种方法是把原始字符串反转,这样最长对称子字符串问题可以转化成求两个字符串的最长公共子字符串问题(备注:不是最长公共子序列)。
有一种可以把复杂度降到O(N)的算法,但是这个算法要利用 suffix tree, 有兴趣的可以搜索一下。
分享到:
相关推荐
代码实现输入任意字符串,并计算输入字符串最大回文长度,并返回回文字符串。
找到字符串中最长的回文子串,并返回其长度
长度为N(N很大)的字符串,求最长回文串
查找一个字符串中的最长回文子串,这里采用的是Manacher算法 比如:cababcaac的最长回文子串就是caac 其中的aba bab也都是回文子串 (Manacher算法) 效率很高的一种查找算法,效率可以达到O(2n+1)
本程序实现功能是在一串长字符串中寻找最长字符串,代码思路清晰,每行代码都有详细注解,方便读者读懂
Manacher算法:求解最长回文字符串,时间复杂度为O(N) 回文串定义:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。回文子串,顾名思义,即字符串中满足回文性质的子串。
字符串中寻找最大的回文字串.zip 字符串中寻找最大的回文字串.zip 字符串中寻找最大的回文字串.zip 字符串中寻找最大的回文字串.zip字符串中寻找最大的回文字串.zip
本文实例为大家分享了js找出字符串中的最长回文串的具体代码,供大家参考,具体内容如下 <!DOCTYPE html> <html> <head> <meta charset=utf-8> <meta ...
# 给你一个字符串a和一个正整数n,判断a中是否存在长度为n的回文子串。 # 如果存在,则输出YES,否则输出NO。 # 回文串的定义:记串str逆序之后的字符串是str1,若str=str1,则称str是回文串,如"abcba". # 输入...
字符串处理- 回文串相关- 求最长回文子串.rar
可实现三种功能: (1)判断一整个字符串是否为回文; (2)判断指定位置的子串是否为回文; (3)输出此字符串中最长的子字符串;
此代码为实现寻找一个长字符串的最大回文序列,回文指两边对称的字符串,分为字符数为奇数和偶数两种情况。
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和xyyxyyx。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应该...
NULL 博文链接:https://louhaiyun.iteye.com/blog/1328996
最长回文子串
该代码,能够输出用户输入字符串中最常的回文串,可直接在vc6.0平台上运行,不过该代码的效率不高,时间复杂度为o[n^2],希望大家多多指教……
C语言判断回文字符串代码