标题：切开字符串
Pear有一个字符串，不过他希望把它切成两段。 这是一个长度为N（<=10^5）的字符串。 Pear希望选择一个位置，把字符串不重复不遗漏地切成两段，长度分别是t和N-t（这两段都必须非空）。
Pear用如下方式评估切割的方案： 定义“正回文子串”为：长度为奇数的回文子串。 设切成的两段字符串中，前一段中有A个不相同的正回文子串，后一段中有B个不相同的非正回文子串，则该方案的得分为A*B。
注意，后一段中的B表示的是：“…非正回文…”，而不是: “…正回文…”。 那么所有的切割方案中，A*B的最大值是多少呢？
【输入数据】 输入第一行一个正整数N（<=10^5） 接下来一行一个字符串，长度为N。该字符串仅包含小写英文字母。 【输出数据】 一行一个正整数，表示所求的A*B的最大值。 【样例输入】 10 bbaaabcaba 【样例输出】 38 【数据范围】 对于20%的数据，N<=100 对于40%的数据，N<=1000 对于100%的数据，N<=10^5
资源约定： 峰值内存消耗 < 512M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
Code
#include <set>
#include <string>
#include <iostream>
using namespace std
;
bool
is_palindrome_string(string str
){
int len
=str
.length();
if(len
%2==0) return false
;
for(int i
=0;i
<len
/2;i
++)
if(str
[i
]!=str
[len
-i
-1])
return false
;
return true
;
}
int main(){
string str
;
set
<string
> temp0
,temp1
;
int N
,Left
[100007],Right
[100007];
cin
>>N
>>str
;
for(int i
=0;i
<N
;i
++){
for(int j
=i
;j
>-1;j
-=2){
int t
=i
-j
+1;
string
s1(str
,j
,t
);
if(is_palindrome_string(s1
))
temp0
.insert(s1
);
}
Left
[i
]=temp0
.size();
}
for(int i
=N
-1;i
>-1;i
--){
for(int j
=i
;j
<N
;j
++){
int t
=j
-i
+1;
string
s1(str
,i
,t
);
if(!is_palindrome_string(s1
))
temp1
.insert(s1
);
}
Right
[i
]=temp1
.size();
}
long long ans
=-1;
for(int i
=1;i
<N
;i
++)
ans
=max(ans
,(long long)Left
[i
-1]*Right
[i
]);
cout
<<ans
<<endl
;
return 0;
}
Alex 007
认证博客专家
机器学习
NLP
TensorFlow
我是 Alex 007，一个热爱计算机编程和硬件设计的小白。为啥是007呢？因为叫 Alex 的人太多了，再加上每天007的生活，Alex 007就诞生了。如果你喜欢我的文章的话，给个三连吧！
