scilab - Scialb 中的回文算法

Question

你能帮我在 Scilab 中构建一个算法，在 n 个元素的零一序列中搜索最长的回文。输出应给出回文的长度和开始搜索序列的字符串中的位置。

例子：对于 111010101100，最长的回文是 110101011。回文的长度是 9，字符串中开始序列的位置是 2。

标签： scilab

Answer 1

这是上述评论中提出的算法的可能实现（对于 n>1）：

x = "10100111000";
n = length(x);
lgmax = 0;
pos = 0;

for i = 1:n-1
    // k=0: odd sequence, k=1: even sequence
    for k = 0:1
        j=1;
        while j <= min(i-1+k,n-i) && part(x,i+j) == part(x,i-j+k)
            j = j+1;
        end
        if 2*j-1-k > lgmax
            lgmax = 2*j-1-k;
            pos = i-j+1+k;
        end
     end
 end

 disp(part(x,pos:pos+lgmax-1))