Suhendry’s Blog

B - Menghitung Palindrom

Author: Suhendry Effendy
Problem: klik di sini

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.

Solusi C/C++
oleh Suhendry Effendy

#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;
}

Solusi PASCAL
oleh Eko Wibowo

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.

• Problem A - Bujur Sangkar Ajaib
• Problem B - Menghitung Palindrom
• Problem C - String Prima
• Daftar Finalis

Pages: 1 2 3 4 5