SSL 1813 回文词 P1435 回文字串[蓝桥杯 2016 省] 密码脱落

SSL 1813 回文词 P1435 回文字串 / [蓝桥杯 2016 省] 密码脱落 题目描述：

题目传送门

---

解题思路：

这里我们可以考虑回文串的两个性质：

1. 回文串正序和倒叙是相同的。
2. 回文串以中选取分割点，左部分正序与右部分倒序是相同的
   如：abbccbba
   左部分正序：abbc
   右部分正序：cbba
   右部分倒叙：abbc

因此我们可以从中作文章，延伸出两种解法。

性质一解法：

可以发现，若要使某个串成为回文串，那么显然要使这个串的倒序与这个串的正序相同。
那么问题就变成了：两个串长度相等，需要插入多少个字母，才能使得这个串的正序与倒序相同。

我们发现，若要使正序与倒序相同，显然两个串的公共子序列可以保留，因为公共子序列本身即是相同的。也就是说我们要插入的仅仅是公共子序列以外的字符。
如：abbb 与 aabb
这两个串的公共子序列可以为 a ，这个公共串的长度为 1 1 1，那么很显然需要插入 l e n − 公 共 子 序 列 长 度 = 3 len-公共子序列 长度=3 len−公共子序列长度=3，即 3 3 3 个字符才能使得两串相同，即：aabbbbb

显然，若要使插入的字符最少，就要使 l e n − 公 共 子 序 列 长 度 len-公共子序列长度 len−公共子序列长度 最小，也就是说公共子序列长度要尽可能的大，因此我们就可以得到：
设最长公共子序列长度为 f f f，串的长度为 l e n len len。
l e n − f len-f len−f

那么最长公共子序列可以怎么找呢，可以参考这里

#include 
#include 
#include 
using namespace std;
int n,ans;
string s,a=" ",b=" ";
unsigned short f[5001][5001]={0},t=0;
int main()
{
	cin>>s;
	n=s.size();
	a=s;
	reverse(s.begin(),s.end());  //将原串倒序得到第二个串
	b=s;
	for(int i=1;i<=n;i++)  //DP找最长公共子序列
	  {
	  	for(int j=1;j<=n;j++)
		  {
		  	if(a[i-1]==b[j-1])
		  	  f[i][j]=f[i-1][j-1]+1;
		  	else
		  	  f[i][j]=max(f[i-1][j],f[i][j-1]);
		  } 
	  }
	cout< 
 
性质二解法： 
性质二的中心思想和性质一 一样，但是性质二考虑的是：将原串的左右部分各插入一些字符，使得左右部分相同。
 问题又回到了原问题，如何用最少的字符插入使得串1与串2相同。很显然，单个串插入的字符数是 
    
     
      
       
        l
       
       
        e
       
       
        n
       
       
        −
       
       
        最
       
       
        长
       
       
        公
       
       
        共
       
       
        子
       
       
        序
       
       
        列
       
      
      
       len-最长公共子序列
      
     
    len−最长公共子序列。
 
若左部分的串为 
    
     
      
       
        a
       
      
      
       a
      
     
    a，则它的长度为 
    
     
      
       
        l
       
       
        e
       
       
        
         n
        
        
         a
        
       
      
      
       len_a
      
     
    lena​，右部分串为 
    
     
      
       
        b
       
      
      
       b
      
     
    b，则它的长度为 
    
     
      
       
        l
       
       
        e
       
       
        
         n
        
        
         b
        
       
      
      
       len_b
      
     
    lenb​，很显然 
    
     
      
       
        l
       
       
        e
       
       
        
         n
        
        
         a
        
       
       
        =
       
       
        l
       
       
        e
       
       
        
         n
        
        
         b
        
       
      
      
       len_a=len_b
      
     
    lena​=lenb​。若 
    
     
      
       
        a
       
      
      
       a
      
     
    a 与 
    
     
      
       
        b
       
      
      
       b
      
     
    b 的最长公共子序列长度为 
    
     
      
       
        f
       
      
      
       f
      
     
    f，则要在 
    
     
      
       
        a
       
      
      
       a
      
     
    a 串中插入 
    
     
      
       
        l
       
       
        e
       
       
        
         n
        
        
         a
        
       
       
        −
       
       
        f
       
      
      
       len_a-f
      
     
    lena​−f 各字符才能使得 
    
     
      
       
        a
       
       
        =
       
       
        b
       
      
      
       a=b
      
     
    a=b；要在 
    
     
      
       
        b
       
      
      
       b
      
     
    b 串中插入 
    
     
      
       
        l
       
       
        e
       
       
        
         n
        
        
         b
        
       
       
        −
       
       
        f
       
      
      
       len_b-f
      
     
    lenb​−f 各字符才能使得 
    
     
      
       
        b
       
       
        =
       
       
        a
       
      
      
       b=a
      
     
    b=a。
 
由于左右部分各要插入字符，因此，插入的总个数为：
 
     
      
       
        
         2
        
        
         ∗
        
        
         (
        
        
         l
        
        
         e
        
        
         
          n
         
         
          a
         
        
        
         −
        
        
         f
        
        
         )
        
       
       
         2*(len_{a}-f) 
       
      
     2∗(lena​−f)
 
 
这里会又疑问，为什么性质一不用乘 
    
     
      
       
        2
       
      
      
       2
      
     
    2 呢？难道它不需要在两个串中同时插入吗？很显然性质一也是要在两个串中同时插入的。但是，性质一中的倒序串只是我们对正序串的一个复制，是一个不存在的虚拟串，也就是说，我们没有必要在一个不存在的倒序串中插入任何字符，只需插入在真实存在中的正序串中即可，因此也就不需要乘 
     
      
       
        
         2
        
       
       
        2
       
      
     2。
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5650908.html