Question

给定一个字符串,往其中插入最少的字符，得到一个回文串，求最小插入字符数。

【问题】
回文是指一个对称的字符串，代表这个串从左往右读和从右往左读是一样的。给定一个字符串,往其中插入最少的字符，得到一个回文串，求最小插入字符数。
【要求】
（1） 应用“数据结构与算法”课程知识建立该问题的数据结构模型；
（2） 编写算法解决问题；
（3） 分析算法的时间性能。
【提示】 计算原字符串与逆序字符串LCS（最长公共子序列长度），用字符串长度减去LCS长度。

Answer 1

program cs;
const n=10000;
var
s:array[1..n] of char;
i,j:integer;
c:string;
begin
readln(c);
if (length(c) mod 2)<>0 then
begin
delete(c,(length(c) div 2)+1,1);
end;
//删去奇数个字符中间字符。

i:=0;j:=1;
while j<=length(c) do
begin
if i=0 then
begin
inc(i);
s[i]:=c[j];
inc(j);
end//栈空，则直接压栈。
else
begin
if s[i]=c[j] then
begin
dec(i);
inc(j);
end//栈顶元素与当前字符相同，就出栈。
else
begin
inc(i);
s[i]:=c[j];
inc(j);
end;//不同，就进栈。
end;
end;
if i=0 then writeln('True')
else writeln('False');//如果栈是空的，证明是回文。
end.
思路是对于奇数个字符，删去中间字符。
其余字符扫一个处理一个，s[]是栈，i是它的指针。
j是c的指针。

追问

用c语言！