2014年10月6日

UVa 12467 - Secret Word

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int MAXLEN = 1111111;
const int MOD = 10007;
const int C1 = 17, C2 = 23;
 
int c1[MAXLEN] = {1}, c2[MAXLEN] = {1};
 
char s1[MAXLEN], s2[MAXLEN];
int len;
 
int h1[MAXLEN], h2[MAXLEN];
int h3[MAXLEN], h4[MAXLEN];
 
void rev(char * s) {
  char * f = s, * t = s;
  while (*t) {
    t++;
  }
  t--;
  while (s < t) {
    char temp = *s;
    *s++ = *t;
    *t-- = temp;
  }
}
 
int hash1(int * h, int a, int b) {
  int result = (h[b] - (h[a - 1] * c1[b - a + 1]) % MOD + MOD) % MOD;
  return result;
}
 
int hash2(int * h, int a, int b) {
  int result = (h[b] - (h[a - 1] * c2[b - a + 1]) % MOD + MOD) % MOD;
  return result;
}

int LCP(int l, int lRev) {
  int ans = 0;
  int minLCP = 0, maxLCP = min(len - l + 1, len - lRev + 1);
  while (minLCP <= maxLCP) {
    int midLCP = (minLCP + maxLCP) / 2;
    int left = l, right = l + midLCP - 1;
    int leftRev = lRev, rightRev = leftRev + midLCP - 1;
    if ((hash1(h1, left, right) == hash1(h2, lRev, rightRev)
        && hash2(h3, left, right) == hash2(h4, lRev, rightRev))) {
      ans = max(ans, midLCP);
      minLCP = midLCP + 1;
    } else {
      maxLCP = midLCP - 1;
    }
  }
  return ans;
}
 
int main() {
  for (int i = 1; i < MAXLEN; i++) {
    c1[i] = (c1[i - 1] * C1) % MOD;
    c2[i] = (c2[i - 1] * C2) % MOD;
  }
  gets(s1);
  int T;
  sscanf(s1, "%d", &T);
  while (T--) {
    gets(s1 + 1);
    sprintf(s2 + 1, "%s", s1 + 1);
    rev(s2 + 1);
    len = strlen(s1 + 1);
    h1[0] = h2[0] = 0;
    h3[0] = h4[0] = 0;
    for (int i = 1; s1[i]; i++) {
      h1[i] = (s1[i] + (h1[i - 1] * C1) % MOD) % MOD;
      h2[i] = (s2[i] + (h2[i - 1] * C1) % MOD) % MOD;
 
      h3[i] = (s1[i] + (h3[i - 1] * C2) % MOD) % MOD;
      h4[i] = (s2[i] + (h4[i - 1] * C2) % MOD) % MOD;
    }
    int maxLCP = 0;
    for (int i = 1; s1[i] && (len - i + 1) > maxLCP; ++i) {
      maxLCP = max(maxLCP, LCP(1, i));
    }
    s1[maxLCP + 1] = 0;
    rev(s1 + 1);
    puts(s1 + 1);
  }
  return 0;
}

沒有留言:

張貼留言