题干：
 

自从 Applese 学会了字符串之后，精通各种字符串算法，比如……判断一个字符串是不是回文串。


这样的题目未免让它觉得太无聊，于是它想到了一个新的问题。

如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串？

输入描述:

仅一行，为一个由字母和数字组成的字符串 s。

输出描述:

如果在插入一个字符之后可以构成回文串，则输出"Yes", 否则输出"No"。

示例1

输入

复制

applese

输出

复制

No

示例2

输入

复制

java

输出

复制

Yes

备注:

|s|≤105

题目大意：

  一句话题意：给定一个字符串,问是否能通过添加一个字母将其变为回文串。

解题报告：

可以认为插入和删除是等价的操作。想到这一点，这题就会好做很多。
如果这个串本身就是回文串，答案一定是Yes。（因为如果原来是奇数个字符，那直接加一个中间的字符就行了；如果原来是偶数个字符，在中间随便加一个字符依旧是回文串。）
否则我们只需要找到串中对称的位置第一对 不相等的两个字符，分别尝试把它们删掉后判断一下是不是回文的就行了。

时间复杂度O(n)。还有中n^2的做法就是枚举每一个删除的位置看删除之后剩下的字符串是否是回文串，但是效率就太低了。。

AC代码：（O(n)的解法）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
bool ok(string s)
{
    string s2=s;
    reverse(s2.begin(),s2.end());
    return s==s2;
}
string str;
int main()
{
	bool flag = 0;
	cin>>str;
	int len = str.size(),i;
    for(i = 0; i<len/2;i++) {
        if(str[i] != str[len-1-i]) break;
    }
    if(i == len/2) flag = 1;
    if(ok(str.substr(i+1,len-2*i-1))) flag = 1;
    if(ok(str.substr(i,len-2*i-1))) flag = 1;
    if(flag) puts("Yes");
	else puts("No"); 
    return 0;
}

TLE代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
bool ok(string s)
{
    string s2=s;
    reverse(s2.begin(),s2.end());
    return s==s2;
}
string str;
int main()
{   
    cin>>str;
    bool flag=0;
    int len = str.size();
    for(int i=0;i<len;++i){
        if(ok(str.substr(0,i)+str.substr(i+1,len-1-i))){
            flag=1;
            break;
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}

一段有待考察的代码：

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<queue>
//#include<map>
//#include<vector>
//#include<set>
//#include<string>
//#include<cmath>
//#include<cstring>
//#define ll long long
//#define pb push_back
//#define pm make_pair
//#define fi first
//#define se second
//using namespace std;
//const int MAX = 2e5 + 5;
//char s1[MAX],s2[MAX],s3[MAX],s4[MAX],c2[MAX],ch;
//int main()
//{
//	cin>>s1;
//	int len = strlen(s1);
//	strcpy(s2,s1);
//	reverse(s2,s2+len);
//	strcpy(c2,s2);
//	for(int i = 0; i<len; i++) {
//		if(s1[i] == s2[i]) continue;
//		ch = s1[i];
//		for(int j = len; j>=i+1; j--) c2[j] = c2[j-1];
//		c2[i] = ch;
//		break;
//	}
//	strcpy(s3,c2);
//	strcpy(s4,s3);
//	reverse(s4,s4+strlen(s3));
//	if(strcmp(s3,s4) == 0) puts("Yes");
//	else puts("No"); 
//	return 0 ;
// }

扩展一个思路：给定一个字符串，问添加几个字符可以构成回文串？

  先把原字符串逆序，然后计算两字符串的最长公共子序列长度，最后diff=字符串长度-最长公共子序列长度，diff即为如果可以形成回文串，原字符串需要添加的字符个数。用到这个题目里，如果diff<=1，即可。时间复杂度O(n^2)。