1.2

• 题目：

给定一个字符串str和str的最长回文子序列strLPS，返回字符串str在任意位置添加最少字符后，整体都是回文串的其中一种结果。
例如：
str = “B1G2TY34I3OPX2S1”;
strLPS = “123I321”;
返回：B1GS2TYXPO34I43OPXYT2SG1B
注意：也可以返回B1SG2XPOTY34I43YTOPX2GS1B，总之返回一种满足条件的结果即可。

---

• 思路
  这是一个剥洋葱的过程，字符串m个字符，子串n个字符，则新串工为2*(m-n)+n=2m-n
  在str左右同时找strLPS的每个字母，找到相同的记录下来，添加不同的值
  比如左1左边是B右1右边是空，故新字符串左右添加B，即B1…1B
  比如左2左边是GS右1右边是空,故新字符串左右添加GS,即B1GS2…2SG1B

---

#include <stdio.h>
#include <string.h>
char str[10000];
char lps[10000];
int main()
{
	freopen("in.txt","r",stdin);
	while(scanf("%s %s",str,lps)!=EOF){
		int len=2*strlen(str)-strlen(lps);
		char res[len];

		int i=0,j=0,k=strlen(str)-1,cnt=0;
		while(j<=k){
			while(str[j]!=lps[i]){
				res[cnt++]=str[j];
				j++;

			}
			while(str[k]!=lps[i]){
				res[cnt++]=str[k];
				k--;
			}
			res[cnt++]=lps[i++];
			j++;k--;
		}
		cnt--;
		for(int i=cnt;i<len;i++){
            res[i]=res[--cnt];
		}
		printf("%s\n",res);
	}
}