问题描述:
对已知字符串S,添加某些字符使之成为回文串。
问题分析:
设A[i,j]为需要添加的长度。
若S[i]=S[j]:A[i,j]=A[i+1,j-1];
若S[i]!=S[j]:A[i,j]=min{A[i+1,j],A[i,j-1]}+1;
根据取等情况反推出添加的位置。
问题描述:
对已知字符串S,添加某些字符使之成为回文串。
问题分析:
设A[i,j]为需要添加的长度。
若S[i]=S[j]:A[i,j]=A[i+1,j-1];
若S[i]!=S[j]:A[i,j]=min{A[i+1,j],A[i,j-1]}+1;
根据取等情况反推出添加的位置。