Submission details
Task:Palindrome
Sender:Kyynel ;_;
Submission time:2016-09-20 17:50:04 +0300
Language:C++
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int edit(std::string, std::string)':
input/code.cpp:9:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int y = 0; y <= s.length(); y++) {
                                 ^
input/code.cpp:10:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x = 0; x <= t.length(); x++) {
                                   ^
input/code.cpp: In function 'bool ok(int)':
input/code.cpp:28:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i + 1 >= s.length()) return false;
                         ^
input/code.cpp: In function 'bool ok2(int)':
input/code.cpp:45:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i + 2 >= s.length()) return false;
                         ^
input/code.cpp: In function 'int main()':
input/code.cpp:61:29: warning: comparison between signed and unsigned integer...

Code

#include <bits/stdc++.h>
#define ll long long
#define N (1<<17)

using namespace std;

int edit (string s, string t) {
  int dp[s.length() + 1][t.length() + 1];
  for (int y = 0; y <= s.length(); y++) {
    for (int x = 0; x <= t.length(); x++) {
      if (x == 0) dp[y][0] = y; 
      else if (y == 0) dp[0][x] = x;
      else dp[y][x] = min(min(dp[y][x - 1] + 1, dp[y - 1][x] + 1), dp[y - 1][x - 1] + (s[y - 1] == t[x - 1] ? 0 : 1));
    }
  }
  return dp[s.length()][t.length()];
}

int ans = 999999999;
string s;
bool ok (int i) {
  string x = s.substr(0, i);
  string y = s.substr(i, s.length() - i);
  reverse(y.begin(), y.end());
  int a = edit(x, y);
  ans = min(ans, a);
  if (((int)s.length()) - i - 1 < 0) return false;
  if (i + 1 >= s.length()) return false;
  x = s.substr(0, i + 1);
  y = s.substr(i + 1, s.length() - i - 1);
  reverse(y.begin(), y.end());
  int b = edit(x, y);
  ans = min(min(a, b), ans);
  return b <= a;
}

bool ok2 (int i) {
  string x = s.substr(0, i);
  string y = s.substr(i + 1, s.length() - i - 1);
  reverse(y.begin(), y.end());
  int a = edit(x, y);
  ans = min(ans, a);
  
  if (((int)s.length()) - i - 2 < 0) return false;
  if (i + 2 >= s.length()) return false;
  x = s.substr(0, i + 1);
  y = s.substr(i + 2, ((int)s.length()) - i - 2);
  reverse(y.begin(), y.end());
  int b = edit(x, y);
  ans = min(min(a, b), ans);
  return b <= a;
}

int main () {
  cin>>s;
  if (s.length() == 1) cout<<0<<endl, exit(0);
  
  int k = s.length();
  int i = 0;
  for (; k >= 1; k /= 2) {
    while (i + k < s.length() && ok(i + k)) i += k;
  }
  int j = 0;
  k = s.length();
  for (; k >= 1; k /= 2) {
    while (j + k < s.length() && ok2(j + k)) j += k;
  }
  
  for (int i2 = max(0, i - 5); i2 < min(i + 6, s.length()); i2++) ok(i2);
  for (int j2 = max(0, j - 5); j2 < min(j + 6, s.length()); j2++) ok2(j2);
  
  cout<<ans<<endl;
}