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

(0)

相关推荐

  • C语言实现统计字符串单词数

    字符串单词数.c #include<stdio.h> #define BUFFERSIZE 1024 int main() { char string[BUFFERSIZE]; int i,count=0,word=0; char c; gets(string) ; for(i=0;(c=string[i])!='\0';i++) { if(c==' ') word=0; else if(word==0) { word=1; count++; } } printf("%d \n&qu

  • C语言中关于sizeof 和 strlen的区别分析

    1.编译时计算运算符sizeof,可用类型或变量做参数,计算占用内存的大小.sizeof后若是类型必须加括弧,若是变量名可不加括弧.sizeof(x)可用来定义数组维数如: 复制代码 代码如下: printf("%d\n", sizeof(short)); 输出的结果为短整型的长度2.用结构类型或变量做参数时,sizeof 返回实际的大小,当用于静态数组时,sizeof 返回全部数组的尺寸.sizeof 操作符不能返回动态地被分派了的数组或外部的数组的尺寸 2.运行时计算strlen,

  • C++不使用变量求字符串长度strlen函数的实现方法

    本文实例讲述了C++不使用变量求字符串长度strlen函数的实现方法.分享给大家供大家参考.具体实现方法如下: 1.strlen的源码实现: size_t strlen(const char *str) //strlen不做内存非法判断,如果是NULL,会core. { const char *eos=str; while(*eos++); return (eos-str-1); } 2.常见面试题会要求不使用额外变量,实现strlen函数: 实现一: int strlen(const char

  • C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st

  • 基于C语言字符串函数的一些使用心得

    就字符串的拼接函数为例strcat.原型:extern char *strcat(char *dest,char *src);用法:#include <string.h>功能:把src所指字符串添加到dest结尾处(覆盖dest结尾处的'\0')并添加'\0'.说明:src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串.      返回指向dest的指针.举例: 复制代码 代码如下: // strcat.c      #include <syslib.h&

  • 探讨编写int strlen(char *strDest);不允许定义变量的问题

    在论坛上看到一位前辈当年的面试题,原话是这样说的"有一次在面试时遇到这样一个问题:不允许调用库函数,也不允许使用任何全局或局部变量编写 int strlen(char *strDest);  ",无意中看到,自己想了一会儿,没有思路,后来整理了各位牛人的回复,觉得采用递归方法解决这个问题,是一种挺好的办法!于是,稍微写了一下代码,算是开拓视野的一点点积累吧! 复制代码 代码如下: #include "stdafx.h"#include <iostream>

  • C语言中字符串和数字的相互转换实现代码

    1.数字转换为字符串sprintf 跟printf 在用法上几乎一样,只是打印的目的地不同而已,前者打印到字符串中,后者则直接在命令行上输出.sprintf 是个变参函数,定义如下: int sprintf( char *buffer, const char *format [, argument] ... ); 除了前两个参数类型固定外,后面可以接任意多个参数.printf 和sprintf 都使用格式化字符串来指定串的格式,在格式串内部使用一些以"%"开头的格式说明符(format

  • c语言输出字符串中最大对称子串长度的3种解决方案

    问题描述: 输入一个字符串,输出该字符串中最大对称子串的长度.例如输入字符串:"avvbeeb",该字符串中最长的子字符串是"beeb",长度为4,因而输出为4. 解决方法:中序遍历 一,全遍历的方法: 1.全遍历的方法,复杂度O(n3); 2.遍历原字符串的所有子串,然后判断每个子串是否对称: 实现方法是:我们让一个指针i从头至尾遍历,我们用另一个指针j从j=i+1逐一指向i后面的所有字符.就实现了原串的所有子串的遍历(子串为指针i到j中间的部分);最后判断得到的

  • java实现输出字符串中第一个出现不重复的字符详解

    java实现输出字符串中第一个出现不重复的字符详解 比如:输入name输出n,输入teeter输出r,输入namename输出null 具体实现代码如下: import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next(); for(int i =0 ; i < str.l

  • Java获取两个字符串中最大相同子串的方法

    "abcwerthelloyuiodef" "cvhellobnm" 思路: 1,将短的那个子串按照长度递减的方式获取到. 2,将每获取到的子串去长串中判断是否包含,如果包含,已经找到! class StringTest3 { public static String getMaxSubString(String s1,String s2) { String max = "",min = ""; max = (s1.lengt

  • C语言计算字符串最后一个单词的长度

    描述: 计算字符串最后一个单词的长度,单词以空格隔开,字符串长度小于5000.(注:字符串末尾不以空格为结尾) 输入描述: 输入一行,代表要计算的字符串,非空,长度小于5000. 输出描述: 输出一个整数,表示输入字符串最后一个单词的长度. 示例: 输入:hello nowcoder.. 输出:8 说明:最后一个单词为nowcoder,长度为8 思路: 首先定义一个变量pos用来找最后一个单词前的空格的位置,找到空格后pos+1就是最后一个单词的首字母位置 2. 其次用s.size()-(pos

  • c语言将字符串中的小写字母转换成大写字母

    描述 给定一个字符串,将其中所有的小写字母转换成大写字母. 输入 输入一行,包含一个字符串(长度不超过100,可能包含空格). 输出 输出转换后的字符串. 样例输入 helloworld123Ha 样例输出 HELLOWORLD123HA #include<iostream> #include<cstdio> #include<cstring> using namespace std; char a[100001]; char ans[1001]; int now; i

  • PHP输出数组中重名的元素的几种处理方法

    1.可以直接用php的内置函数array_intersect() array array_intersect ( array $array1 , array $array2 [, array $ ... ] ) array_intersect() 返回一个数组,该数组包含了所有在 array1 中也同时出现在所有其它参数数组中的值.注意键名保留不变. 代码: 复制代码 代码如下: <?php $array1 = array("a" => "green",

  • 使用C语言提取子字符串及判断对称子字符串最大长度

    先来看一个使用C语言从字符串中提取子字符串的基本方法总结: #include <stdio.h> /*处理中文字符*/ /*遍历字符串,非ASCII字符读取2个字节,ASCII读取一个字节,获取字符串长度*/ int StrLenU(const char* string) { int len = 0 ; const char* p = string; while(*p++ != '\0') { if(*p > 0x80 || *p < 0) { p++; } len++; } re

  • C语言如何实现翻转字符串中的单词

    目录 C语言翻转字符串中的单词 另外开辟一个空间,来存放翻转的字符串 直接在原数组上进行操作 C语言字符串各单词的反转 思路 代码实现 代码编译 调试输出 C语言翻转字符串中的单词 另外开辟一个空间,来存放翻转的字符串 单词之间是以空格间隔的,所以我们翻转需要一个一个字符进行翻转,我们需要找寻空格,找到空格表示一个字符已经找到,进行以下的步骤: 1. 首先获取原字符串的长度,申请一个长度+1的空间,因为还需要一个结束符. 2. 定义一个变量i,初始化为0,用i进行字符串的遍历,定义一个start

  • C语言实现字符串操作函数的实例

    C语言实现字符串操作函数的实例 在编写程序的过程中,我们经常使用到一些字符串函数,例如求字符串长度,拷贝字符串--,这些函数都在C标准库中存在,我们可以直接使用.但我们还需要掌握这些函数的实现方法,今天来看看一些常用的字符串操作函数的实现方法. 1.strlen strlen是用来求字符串长度的函数,字符串长度就是它所包含的字符个数. 今天给大家介绍三种实现strlen函数的方法 (1)定义一个计数器count //方式一:定义一个计数器 size_t my_strlen(const char

  • JavaScript访问字符串中单个字符的两种方法

    概述 JavaScript是一门很灵活的语言,也提供了很多原生的函数供我们编程使用.这篇文章主要对javascript中如何访问字符串中的单个字符做一下介绍. javascript中一切皆为对象,要访问字符串中的单个字符主要有两种方法:数组索引和charAt()函数. 索引和charAt() 索引方式访问单个字符串 在javascript中,字符串可以被当做数组来处理,所以我们可以用数组下标的方式来访问单个字符.代码如下: 复制代码 代码如下: <script type="text/jav

随机推荐