C++中实现最大回文子串(二)

  01.// huiwen.cpp : 定义控制台应用程序的入口点。
    02.//
    03.
    04.#include "stdio.h"
    05.#include "stdlib.h"
    06.#include "iostream"
    07.
    08.using namespace std;
    09.
    10.bool isHuiwen（char * str）；
    11.bool isHuiwen2（char * ps, char * pn）；
    12.char * findBiggestHuiwen（char * str）；
    13.char * findBiggestCommon（const char * str1, const char * str2）；
    14.char * findBiggestHuiwen2（char * str）；
    15.
    16.
    17.int main（int argc, char * argv[]）
    18.{
    19.    char str[] = "123456";
    20.
    21.    cout《sizeof（str）《endl;
    22.    bool result = isHuiwen（str）；
    23.    cout《str《":"《result《endl;
    24.
    25.    char str2[] = "123456654321";
    26.    bool result2 = isHuiwen（str2）；
    27.    cout《str2《":"《result2《endl;
    28.
    29.    char str3[] = "123454321";
    30.    bool result3 = isHuiwen（str3）；
    31.    cout《str3《":"《result3《endl;
    32.
    33.    char str4[] = "abcde123321d";
    34.    char * p = findBiggestHuiwen（str4）；
    35.    cout《str4《":"《p《endl;
    36.
    37.    char str5[] = "123454321abcdefg";
    38.    char * p1 = findBiggestHuiwen（str5）；
    39.    cout《str5《":"《p1《endl;
    40.
    41.    // 查找最长公共子串
    42.    char s1[] = "123456abcd";
    43.    char s2[] = "123456iiiijjkklj";
    44.    char * p2 = findBiggestCommon（s1, s2）；
    45.    cout《p2《endl;
    46.
    47.    char s3[] = "abcdeftkadkkajslasdf123";
    48.    char s4[] = "ei123wa";
    49.    char * p3 = findBiggestCommon（s3, s4）；
    50.    cout《p3《endl;
    51.
    52.
    53.    // 查找最大回文2
    54.    char z1[] = "123454321abcdefg";
    55.    char * x1 = findBiggestHuiwen2（z1）；
    56.    cout《z1《":"《x1《endl;
    57.
    58.    system（"pause"）；
    59.    return 0;
    60.}
    61.
    62.// 通过遍历所有的子串查找最大回文
    63.char * findBiggestHuiwen（char * str）
    64.{
    65.    char * presult;
    66.    char * ps = str;
    67.    char * pn = str;
    68.    while（*pn != '\0'） pn++;
    69.    pn--;
    70.
    71.    int max = 0;
    72.
    73.    while（ps < pn）
    74.    {
    75.        // 判断以ps开始的每一个字符串
    76.        // 移动pn获取以ps开始的每个字符串
    77.        char * pend = pn;
    78.        while（pend > ps）
    79.        {
    80.            if（isHuiwen2（ps, pend））
    81.            {
    82.                int length = pend - ps + 1;
    83.                if（max < length）
    84.                {
    85.                    max = length;
    86.                    presult = ps;
    87.                }
    88.            }
    89.
    90.            pend--;
    91.        }
    92.
    93.        ps++;
    94.    }
    95.
    96.    char * result = （char *）malloc（sizeof（char）*（max + 1））；
    97.    for（int i = 0; i < max; i++）
    98.        result[i] = *presult++;
    99.    result[max] = '\0';
    100.    return result;
    101.}
    102.
    103.// 通过查找两个字符串的最大子串来查找最大的回文
    104.char * findBiggestHuiwen2（char * str）
    105.{
    106.    if（str == NULL） return NULL;
    107.    char * ps = str;
    108.    char * pn =str;
    109.    while（*pn != '\0'） pn++;
    110.    pn--;
    111.
    112.    char * str2 = （char *）malloc（sizeof（char）*（strlen（str） + 1））；
    113.    strcpy（str2, str）；
    114.    while（ps<=pn）
    115.    {
    116.        char temp = *ps;
    117.        *ps = *pn;
    118.        *pn = temp;
    119.        ps++;pn--;
    120.    }
    121.
    122.    char * result = findBiggestCommon（str, str2）；
    123.    return result;
    124.}
    125.
    126.bool isHuiwen2（char * ps, char * pn）
    127.{
    128.    if（ps >= pn） return false;
    129.    while（ps <= pn）
    130.    {
    131.        if（*ps != *pn）
    132.            break;
    133.        else
    134.        {
    135.            ps++;
    136.            pn--;
    137.        }
    138.    }
    139.
    140.    if（ps <= pn） return false;
    141.    else return true;
    142.}
    143.
    144.
    145.bool isHuiwen（char * str）
    146.{
    147.    if（str == NULL） return false;
    148.    if（strlen（str） <= 1） return false;
    149.
    150.    char * ps = str;
    151.    char * pn = str;
    152.    while（*pn != '\0'）
    153.        pn++;
    154.    pn--;
    155.
    156.    while（ps<=pn）
    157.    {
    158.        if（*ps != *pn）
    159.            break;
    160.        else
    161.        {
    162.            ps++;
    163.            pn--;
    164.        }
    165.    }
    166.
    167.    if（ps<=pn） return false;
    168.    else return true;
    169.}
    170.
    171.// 查找最大的公共子串
    172.char * findBiggestCommon（const char * str1, const char * str2）
    173.{
    174.    int length = 0;
    175.    int length1 = strlen（str1）；
    176.    int length2 = strlen（str2）；
    177.    char * p;
    178.    int C[50][50] = {0};
    179.    int start = 0;
    180.    int end = 0;
    181.
    182.    for（int i = 0; i < length1; i++）
    183.    {
    184.        for（int j = 0; j < length2; j++）
    185.        {
    186.            if（str1[i] == str2[j]）
    187.            {
    188.                if（i==0 || j==0）
    189.                {
    190.                    C[i][j] = 1;
    191.                }
    192.                else
    193.                {
    194.                    C[i][j] = C[i - 1][j - 1] + 1;
    195.                }
    196.
    197.                if（C[i][j] > length）
    198.                {
    199.                    end = j;
    200.                    length = C[i][j];
    201.                }
    202.            }
    203.        }
    204.    }
    205.
    206.    start = end - length + 1;
    207.    p = （char *）malloc（sizeof（char）*（length + 1））；
    208.    for（int i = start; i <=end; i++）
    209.        p[i - start] = str2[i];
    210.    p[length] = '\0';
    211.    return p;
    212.}