hdu 1544 连续回文子串的个数构造法

发布时间：2020-12-13 20:09:55 所属栏目：PHP教程来源：网络整理

导读：思路：子串的长度只能为奇数或偶数（长度为1的不算，直接特判）。对长度为奇数的子串，以 2 到 n 之间的数为该子串的中心，然后分别向两边扩大，只要碰到1个子串扩大不满足回文的，就退出。对偶数长度的子串分别以1到n - 1之间的数为左，该数右侧的数为右

思路：

子串的长度只能为奇数或偶数（长度为1的不算，直接特判）。

对长度为奇数的子串，以 $2$ 到 $n$ 之间的数为该子串的中心，然后分别向两边扩大，只要碰到1个子串扩大不满足回文的，就退出。
对偶数长度的子串分别以1到n - 1之间的数为左，该数右侧的数为右，组成两个数，然后再拿这两个数扩大。

代码：

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream> //hdu 1544,
using namespace std;
typedef long long int LL;
const int M = 100009,INF = 0x3fffffff;
string str;
int n;

LL odd(void) {
    LL o = 0;
    for(int i = n - 2; i > 0; i--) {
        for(int j = 1; j <= min(n - i - 1,i); j++) {
            if(str[i + j] == str[i - j]) o++;
            else break;
        }
    }
    return o;
}

LL even(void) {
    LL e = 0;
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j <= min(i,n - i - 2); j++) {
            if(str[i - j] == str[i + j + 1]) e++;
            else break;
        }
    }
    return e;
}

int main(void) {
    while(cin >> str) {
        //for(int i = 0; i < 5000; i++) str += 'a';
        n = str.size();
        cout << odd() + even() + n << endl;
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

hdu 1544 连续回文子串的个数 构造法

思路：

hdu 1544 连续回文子串的个数构造法