c语言输出字符串中最大对称子串长度的3种解决方案
问题描述:
输入一个字符串,输出该字符串中最大对称子串的长度。例如输入字符串:“avvbeeb”,该字符串中最长的子字符串是“beeb”,长度为4,因而输出为4。
解决方法:中序遍历
一,全遍历的方法:
1.全遍历的方法,复杂度O(n3);
2.遍历原字符串的所有子串,然后判断每个子串是否对称;
实现方法是:我们让一个指针i从头至尾遍历,我们用另一个指针j从j=i+1逐一指向i后面的所有字符。就实现了原串的所有子串的遍历(子串为指针i到j中间的部分);
最后判断得到的子串是否对称即可;
二,此外还有个巧妙的方法,值得和大家分享一下(这是自己想的哦,转载请注明出处):
原串是str1=“avvbeeb”,将其翻转得到str2=“beebvva”,然后错位比较:
1: avvbeeb
str2:beebvva (上下对齐的元素是a;a比较)
2: avvbeeb
str2:beebvva (上下对齐的量元素av;va比较,不对称)
…………
11: avvbeeb
str2: beebvva (上下对齐的量元素beeb;beeb比较,得到最长对称子串)
…………
该方法要移动m+n次,每次元素比较个数从1到m不等,复杂度O(n2);
三,最值得推荐的还是下面的方法,复杂度O(n):
(以下都是自己想的自己写的,码字实在辛苦,转载请注明出处)
1.起始这道题分析起来非常扯淡,花了我两天的空闲时间才搞定!
2.分析过程如下:
3. 1-k位的元素中,其中最长对称子串(包含第k位元素)长度为f(n),我们讨论f(n+1)与f(n)的关系;
4.比如 b xxx a其中xxx代表对称子串,a为第n+1位元素,我们现在求f(n+1);
5.我们分析所有情况:(我们用xxx代表n位对称子串)
数组A存放字符数组;
f(n)表示f(n)位元素对应子串长度;
分析如下A[n+1]=a的子串长度值f(n+1)值是多少:
1:bxxxa :A[n+1]位元素a与对称子xxx串前的一位元素b不同时;
1.1: a与左相邻元素不同,即xxx=bxb时,bbxba不是对称子串,f(n+1)=1;
1.2: a与左相邻元素相同,即xxx=axa时,baxaa,如果是对称子串,则x这个未知部分必须全部是a,即
baaaa,f(n+1)=f(n)+1,否则不是对称子串f(n+1)=1;
axxxa :A[n+1]位元素a与对称子串前一位元素相同;
2.这种情况f(n+1)位元素a与其左相邻元素是否相同都不影响f(n+1)的结果,
比如:a bacab a a aaaaa a
串长:1 13135 7 1 23456 7 也就是xxx不论是何种情况的对称串,f(n+1)=f(n)+2;
6.综上分析,串A[n+1]位的值f(n+1)只和串中第A[n]位字符以及第A[n-f(n)-1]有关;
(5中分析的f(n+1)=1的情况可以忽略不考虑,因为最小对称子串值>=1)
1: A[n+1]和A[n-f(n)-1]相同;
a xxx x a :acca aaaa acdca
A[n-f(n)-1] A[n] A[n+1]
f(n) f(n+1) :1124 1234 11134
此时f(n+1)=f(n)+2;
2: A[n+1]和A[n-f(n)-1]不同;A[n+1]和A[n]相同;
如: b xxx a a :bcacaa baaaaa
A[n-f(n)-1] A[n] A[n+1] :111332 112345
此时f(n+1)与它前面有几个a有关;
综上分析代码如下:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int FUN(char *inp){//求最大对称子串长度
int maxlen = 1;//最大长度
int len=strlen(inp);
int record[len];//存包含该位及前个元素最长对称子串
record[0]=1;
int i=1;
for(;i<len;i++){
int max =1;
if((i-record[i-1]-1)>=0 && inp[i] == inp[i-record[i-1]-1]){
max = max>(record[i-1] + 2)? max:(record[i-1] +2);
}
int k = 1;
while(inp[i] == inp[i-k]){
k++;
}
max = max>k? max:k;
record[i] = max;
printf("----- is:%d\n",record[i]);
if(record[i]>maxlen) maxlen=record[i];
}
return maxlen;
}
int main(){
char *input="abadddkeipdldlfk";
int retlen = FUN(input);//从前向后递归
printf("max length is:%d\n",retlen);
return 0;
}
输出结果:
xu@xu-ThinkPad-X61:~/algorithm$ gcc LongSunmetricSub.c
xu@xu-ThinkPad-X61:~/algorithm$ ./a.out
----- is:1
----- is:3
----- is:1
----- is:2
----- is:3
----- is:1
----- is:1
----- is:1
----- is:1
----- is:1
----- is:1
----- is:3
----- is:1
----- is:1
----- is:1
max length is:3
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 这篇文章介绍了C#判断字符串是否数字或字母的实例,有需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了PostgreSQL判断字符串是否包含目标字符串的多种方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 本文实例讲述了php字符串按照单词进行反转的方法。分享给大家供大家参考。具体分析如下:下面的php代码可以将字符串按照单词进行反转输出,实际上是现将字符串按照空格分隔到数组,然后对数组进行反转输出。...2015-03-15
- 这篇文章主要介绍了使用list stream:任意对象List拼接字符串操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-09
- 这篇文章主要介绍了MySQL 字符串拆分操作(含分隔符的字符串截取),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-22
- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- JS中默认中文字符长度和其它字符长度计算方法是一样的,但某些情况下我们需要获取中文字符串的实际长度,代码如下: 复制代码 代码如下: function strLength(str) { var realLength = 0, len = str.length, charCode = -1;...2014-06-07
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C#实现字符串转换成字节数组的简单实现方法,仅一行代码即可搞定,非常简单实用,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 文章介绍一个实用的函数,我们如果用php substr来截取字符在中文上处理的很有问题,今天自己写了一个比较好的中文与英文字符截取的函数,有需要的朋友可以参考下。 ...2016-11-25
- 这篇文章主要介绍了C#实现对字符串进行大小写切换的方法,涉及C#操作字符串的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#将字节数组转成易读的字符串的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了PostgreSQL 字符串处理与日期处理操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-01