腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

c語言輸出字符串中最大對稱子串長度的3種解決方案

更新時間：2014年03月13日 16:41:01 作者：

這篇文章主要介紹了c語言輸出字符串中最大對稱子串長度的3種解決方案,需要的朋友可以參考下

問題描述：

輸入一個字符串，輸出該字符串中最大對稱子串的長度。例如輸入字符串：“avvbeeb”，該字符串中最長的子字符串是“beeb”，長度為4，因而輸出為4。

解決方法：中序遍歷

一，全遍歷的方法：

1.全遍歷的方法，復(fù)雜度O（n3）;

2.遍歷原字符串的所有子串，然后判斷每個子串是否對稱；

實現(xiàn)方法是：我們讓一個指針i從頭至尾遍歷，我們用另一個指針j從j=i+1逐一指向i后面的所有字符。就實現(xiàn)了原串的所有子串的遍歷（子串為指針i到j(luò)中間的部分）;
最后判斷得到的子串是否對稱即可;

二，此外還有個巧妙的方法，值得和大家分享一下（這是自己想的哦，轉(zhuǎn)載請注明出處）：

原串是str1=“avvbeeb”，將其翻轉(zhuǎn)得到str2=“beebvva”，然后錯位比較：

1： avvbeeb

str2：beebvva （上下對齊的元素是a;a比較）

2： avvbeeb

str2：beebvva （上下對齊的量元素av;va比較，不對稱）

…………

11： avvbeeb

str2： beebvva （上下對齊的量元素beeb;beeb比較，得到最長對稱子串）

…………

該方法要移動m+n次，每次元素比較個數(shù)從1到m不等，復(fù)雜度O（n2）;

三，最值得推薦的還是下面的方法，復(fù)雜度O（n）：

（以下都是自己想的自己寫的，碼字實在辛苦，轉(zhuǎn)載請注明出處）

1.起始這道題分析起來非常扯淡，花了我兩天的空閑時間才搞定！

2.分析過程如下：

3. 1-k位的元素中，其中最長對稱子串（包含第k位元素）長度為f（n），我們討論f（n+1）與f（n）的關(guān)系;

4.比如 b xxx a其中xxx代表對稱子串，a為第n+1位元素，我們現(xiàn)在求f（n+1）;

5.我們分析所有情況：（我們用xxx代表n位對稱子串）

數(shù)組A存放字符數(shù)組;

f（n）表示f（n）位元素對應(yīng)子串長度;

分析如下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）的結(jié)果，

比如：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]有關(guān);

（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有關(guān);

綜上分析代碼如下：

復(fù)制代碼代碼如下:

#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;
}

輸出結(jié)果：

復(fù)制代碼代碼如下:

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