2013年3月24日

UVa 10100 - Longest Match


#include <stdio.h>
#include <string.h>

int max(int a, int b) {
  return a > b ? a : b;
}

int isch(char c) {
  if (c >= '0' && c <= '9') return 1;
  if (c >= 'a' && c <= 'z') return 1;
  if (c >= 'A' && c <= 'Z') return 1;
  return 0;
}

int chk(char * s) {
  int i;
  for (i = 0; s[i]; i++)
    if (!isch(s[i])) return 0;
  return i;
}

char v1[999][999], v2[999][999];

int main() {
  int T = 1;
  char s1[1005], s2[1005];
  while (gets(s1)) {
    gets(s2);
    memset(v1, 0, sizeof(v1));
    memset(v2, 0, sizeof(v2));
    int i, j, n1 = 1, n2 = 1, l = 0;
    for (i = 0; ; i++)
      if (isch(s1[i])) {
        v1[n1][l++] = s1[i];
      } else {
        v1[n1][l] = 0;
        if (chk(v1[n1])) n1++;
        else v1[n1][0] = 0;
        l = 0;
        if (!s1[i]) break;
      }
    for (i = 0; ; i++)
      if (isch(s2[i])) {
        v2[n2][l++] = s2[i];
      } else {
        v2[n2][l] = 0;
        if (chk(v2[n2])) n2++;
        else v2[n2][0] = 0;
        l = 0;
        if (!s2[i]) break;
      }
    int dp[300][300] = {};
    for (i = 1; i <= n1; i++)
      for (j = 1; j <= n2; j++)
        if (!strcmp(v1[i], v2[j]) && chk(v1[i])) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    if (s1[0] && s2[0]) printf("%2d. Length of longest match: %d\n", T++, dp[n1][n2]);
    else printf("%2d. Blank!\n", T++);
  }
  return 0;
}

沒有留言:

張貼留言