B - Menghitung Palindrom

Dengan panjang string tidak lebih dari 100, solusi O(n³) dengan cara bruteforce sudah cukup untuk menyelesaikan soal ini. Yang perlu kita lakukan hanya menguji semua substring yang bisa dibentuk.

Bagaimana jika panjang string tidak lebih dari 1000? Untuk ini kita perlu mengoptimasi solusi kita menjadi O(n²). Hal ini bisa dilakukan dengan melakukan bruteforce hanya pada titik tengah palindrom, kemudian diuji seberapa banyak palindrom yang bisa dibentuk dengan titik tengah tersebut (Ekspansi ke kiri dan kanan).

36 peserta berhasil menyelesaikan soal ini.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

bool ispalin(char s[], int a, int b) {
  while ( a <= b ) {
    if ( s[a] != s[b] ) return false;
    a++, b--;
  }
  return true;
}

int main()
{
  int T;
  scanf( "%d", &T );

  while ( T-- ) {
    char s[105];
    scanf( "%s", s );
    int len = strlen(s);
    int ans = 0;
    for ( int i = 0; i < len; i++ )
      for ( int j = i; j < len; j++ )
        if ( ispalin(s,i,j) ) ans++;
    printf( "%d\n", ans );
  }

  return 0;
}

function ispalin(s:string; a, b:longint): boolean;
  begin
  while ( a <= b ) do
  begin
    if ( s[a] <> s[b] ) then
    begin
      ispalin := false;
    exit;
    end;
    a := a + 1;
    b := b - 1;
  end;
  ispalin := true;
end;

var
  T, i, j, len, ans: longint;
  s: string;
begin
  readln(T);
  while ( T > 0 ) do
  begin
    T := T - 1;
    readln(s);
    len := length(s);
    for i := 1 to len do
      for j := i to len do
        if ( ispalin(s,i,j) ) then ans := ans + 1;
    writeln(ans);
  end;
end.