阅读程序-2解析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**************************************************************** 
 * Description: 2016_S_25
 * Author: Alex Li
 * Date: 2023-09-07 11:44:05
 * LastEditTime: 2023-09-07 12:22:39
****************************************************************/
#include <iostream>
using namespace std;
int lps(string seq, int i, int j)//i是字符串左侧的起始点标识，j是字符串是右侧起始点标识
{
    int len1, len2;
    if (i == j)//如果i=j说明长度是1，回文长度也是1
        return 1;
    if (i > j)    //左边界大于右边界，区间不存在，返回0
        return 0;
    if (seq[i] == seq[j])//[i]字符和[j]字符相同，回文数+2，左右各进一格，继续递归
        return lps(seq, i + 1, j - 1) + 2;
    len1 = lps(seq, i, j - 1); //如果[i]和[j]字符不同，[j-1]右侧缩进一格，递归
    len2 = lps(seq, i + 1, j); //如果[i]和[j]字符不同，[j+1]左侧缩进一格，递归
    if (len1 > len2)
        return len1;
    return len2;  //返回两个子串的最大值
}
int main()
{
    string seq = "acmerandacm"; //原始字符串
    int n = seq.size(); //字符串大小
    cout << lps(seq, 0, n - 1) << endl; //函数调用
    return 0;
}