[HDU 1020] Encoding

Encoding

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Problem Description

Given a string containing only 'A' - 'Z', we could encode it using the following method:

1. Each sub-string containing k same characters should be encoded to "kX" where "X" is the only character in this sub-string.

2. If the length of the sub-string is 1, '1' should be ignored.

Input

The first line contains an integer N (1 <= N <= 100) which indicates the number of test cases. The next N lines contain N strings. Each string consists of only 'A' - 'Z' and the length is less than 10000.

Output

For each test case, output the encoded string in a line.

Sample Input

ABC

ABBCCC

Sample Output

ABC

A2B3C

AC Code

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <assert.h>
  5  
  6 #define MAXLEN 10010
  7  
  8  
  9 char * Encording(const char * pszBuf)
 10 {
 11     int iNum = 0;
 12     int iNumLen = 0;
 13     int iLen = 0;
 14     int i = 0;
 15     int j = 0;
 16     int k = 0;
 17     char * pszResult = NULL;
 18  
 19     assert(pszBuf != NULL);
 20  
 21     iLen = strlen(pszBuf);
 22  
 23     pszResult = (char *)malloc(sizeof(char)* (iLen + 1));
 24  
 25     if (NULL == pszResult)
 26     {
 27         return NULL;
 28     }
 29  
 30     memset(pszResult, 0, sizeof(char)* (iLen + 1));
 31  
 32     for (i = 0; i < iLen; i++)
 33     {
 34         iNum = 0;
 35         for (j = i + 1; j < iLen; j++)
 36         {
 37             if (*(pszBuf + i) == *(pszBuf + j))
 38             {
 39                 iNum = j - i + 1;
 40                 continue;
 41             }
 42             else
 43             {
 44                 break;
 45             }
 46         }
 47  
 48         if (iNum > 1)
 49         {
 50             iNumLen = sprintf(pszResult + k, "%d", iNum);
 51             *(pszResult + k + iNumLen) = *(pszBuf + i);
 52             k += iNumLen + 1;
 53             i += iNum - 1;
 54         }
 55         else
 56         {
 57             *(pszResult + k) = *(pszBuf + i);
 58             k++;
 59         }
 60     }
 61  
 62     return pszResult;
 63 }
 64  
 65  
 66 #ifdef ONLINE_JUDGE
 67 int main()
 68 {
 69     int iTotalLine = 0;
 70     char *pszTmp = NULL;
 71     char *pszResult = NULL;
 72  
 73     pszTmp = (char *)malloc(sizeof(char)* (MAXLEN + 1));
 74  
 75     if (NULL == pszTmp)
 76     {
 77         return -1;
 78     }
 79  
 80     while (scanf("%d", &iTotalLine) != EOF)
 81     {
 82         assert((1 <= iTotalLine) && (iTotalLine <= 100));
 83         while (iTotalLine--)
 84         {
 85             memset(pszTmp, 0, sizeof(char)* (MAXLEN + 1));
 86  
 87             scanf("%s", pszTmp);
 88             pszResult = Encording(pszTmp);
 89             if (NULL == pszResult)
 90             {
 91                 free(pszTmp);
 92                 pszTmp = NULL;
 93                 return -1;
 94             }
 95             printf("%s
", pszResult);
 96  
 97             free(pszResult);
 98             pszResult = NULL;
 99         }
100     }
101  
102     free(pszTmp);
103     pszTmp = NULL;
104  
105     assert(pszResult == NULL);
106  
107     return 0;
108 }
109 #endif

View Code

TestCase

 1 class OJTest : public testing::Test
 2 {
 3 protected:
 4     virtual void SetUp()
 5     {
 6         m_pszResult = NULL;
 7     }
 8     virtual void TearDown()
 9     {
10         free(m_pszResult);
11         m_pszResult = NULL;
12     }
13 protected:
14     char * m_pszResult;
15 };
16  
17 TEST_F(OJTest, TestCase01)
18 {
19     m_pszResult = Encording("ABC");
20     ASSERT_STREQ("ABC", m_pszResult);
21 }
22  
23 TEST_F(OJTest, TestCase02)
24 {
25     m_pszResult = Encording("ABBCCC");
26     ASSERT_STREQ("A2B3C", m_pszResult);
27 }
28  
29 TEST_F(OJTest, TestCase03)
30 {
31     m_pszResult = Encording("ABBCBBAACC");
32     ASSERT_STREQ("A2BC2B2A2C", m_pszResult);
33 }
34  
35 TEST_F(OJTest, TestCase04)
36 {
37     m_pszResult = Encording("AAAAAAAAAAABC");
38     ASSERT_STREQ("11ABC", m_pszResult);
39 }

View Code