ural 1297 [复制链接]

ural 1297 Palindrome 最长的回文串

Time Limit: 1.0 second
Memory Limit: 1 000 КБ

给定一个字符串，长度在1000以内.

求最长的连续子串，并且是回文串（如果长度相同找最靠前面的）。

Sample Input

ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA



Sample Output

ArozaupalanalapuazorA

我的做法：

方法1： for i:=1 to len -1 do
            for j:=i to len do ...
方法2： 枚举回文串的中间点，分奇、偶两种情况判断~~~从中间点左右依次向两头判断。
方法3： 1：我们可以靠碍的方法判断一个在 S 中长度为 L 的子字符串是不是回文串。
      2：同 2 分法从 1~N 中求出最大的满主条件的 L 。


唯一的问题是，以上3种算法的复杂度分别是多少？？？

1 n^2
2 n log n（lca)
3 和2有何不一样

不明 不白~~~

program Ural_1297(Input, Output);
const
    MaxN = 1000;
type
    TIndex = Longint;
    TChar = array[1..MaxN] of Char;
    TNext = array[1..MaxN] of TIndex;
    TLast = array['A'..'z'] of TIndex;
var
    N: TIndex;
    P: TNext;
    L: TLast;
    S: TChar;
    MaxLength, MaxIndex: TIndex;

procedure Main;
var
    Ch: Char;
    i, j, k: TIndex;
    Valid: Boolean;
begin
    FillChar(P, SizeOf(P), 0);
    FillChar(L, SizeOf(L), 0);
    FillChar(S, SizeOf(S), 0);
    N := 0;
    while not Eoln do
    begin
        Read(Ch);
        if Ch in ['A'..'Z', 'a'..'z'] then
        begin
            Inc(N);
            S[N] := Ch;
            if L[Ch] > 0 then P[L[Ch]] := N;
            L[Ch] := N;
        end;
    end;
    if N = 0 then Exit;
    MaxLength := 1;
    MaxIndex := 1;
    for i := 1 to N do
    begin
        j := i;
        repeat
            j := P[j];
            if j = 0 then Break;
            if (j - i + 1) <= MaxLength then Continue;
            Valid := true;
            for k := 1 to (j - i - 1) div 2 do
                if S[i + k] <> S[j - k] then
                begin
                    Valid := false;
                    Break;
                end;
            if Valid then //Current must be larger then MaxLenth
            begin
                MaxIndex := i;
                MaxLength := j - i + 1;
            end;
        until false;
    end;
    for i := 1 to MaxLength do
        Write(S[MaxIndex + i - 1]);
    Writeln;
end;
begin
{  Assign(Input, 'i.txt');
    Reset(Input);
    Assign(Output, 'o.txt');
    Rewrite(Output); }
    Main;
    {Close(Input);
    Close(Output);    }
end.

...