嗯，照旧，据传说是MS/Google等等IT名企业的面试题：

在非常老的Word版本里面，为了排版的需要，提供了两边对齐

当时的方法是通过在英文单词中间均匀插空格，来保持一行的两端都是字符而中间看起来又比较均匀

请实现这个功能

BTW: 注意不要吃掉字符哦，时间和空间都很重要，尽量追求O(1)的空间+O(n)的时间

贴个Haskell的实现。空间O(1)是做不到的。。。呵呵，刚学Haskell不久，写的很丑。

align2side :: String -> Int -> String  --传入字符串和行宽度，传出字符串
align2side s width = 
    let needFillLength = width - (length s)
        needFillCount = (length s) - 1
        fillSpaceLength = floor(fromIntegral(needFillLength) / fromIntegral(needFillCount))
        rest = needFillLength - (fillSpaceLength * needFillCount)
    in  case fillSpaceLength of 0 -> align2side_sub1 s needFillLength --剩余空格不足以在每个字母后插入至少一个空格
                                otherwise -> align2side_sub2 s (take fillSpaceLength (repeat ' ')) rest

align2side_sub1 :: String -> Int -> String
align2side_sub1 [] _ = []
align2side_sub1 s 0 = s
align2side_sub1 (x:xs) needFillLength = ([x] ++ " ") ++ align2side_sub1 xs (needFillLength - 1)

align2side_sub2 :: String -> String -> Int -> String --传入字符串，每个字母后需填充的空格和剩余空格
align2side_sub2 [] _ _ = [] --字符串到尾部时结束
align2side_sub2 (x:xs) fillspace rest
    | xs == [] = (take rest (repeat ' ')) ++ [x] --如果是最后一个字母，加上剩余空格
    | otherwise = ([x] ++ fillspace) ++ align2side_sub2 xs fillspace rest

正好有空，随便写两行练练。

/** Insert spaces for line justify. */
char * foo( char * str, int to_len ) {
  char * p;
  int n_ins, n_len;

  if ( str == NULL )
    return NULL;

  /** to thread safe, need block data access. (start) */

  for ( p=str, n_len=n_ins=0; *p; p++, n_len++ )
    if ( *p == ' ' )
      n_ins++;

  if ( n_ins ) {
    int c, i_left = to_len - n_len;
    char * p_left = p;

    p += i_left;
    *p = 0;

    while ( n_ins ) {
      i_left -= c = i_left / n_ins--;
      while ( *--p = *--p_left ) != ' ' );
      while ( c-- )
        *--p = ' ';
    }
  }

  /** to thread safe, need block data access. (end) */

  return str;
}

//========字符对齐===========

//这个算法可以处理一个字符串里面的任意多个空格，任意的位置，使空格均匀分布在单词之间（如果只考虑多   // 余的空格在字符串的最后面，就可以省略第一步）
//主要分为两大步，1，把所有单词移到string的最前面，用一个空格隔开
//2.通过计算每个单词应该有多少空格（注意：可能不是均匀分布，比如说有28个空格，6个单词，这样
//有的单词间有5个，有的有6个
// 3. 移单词，插入空格  
void foo_str(char* str, int n)
{
    if(str == NULL)
    {
        return;
    }
    int length = 0;
    char* p = str;
    int wordCount=0;
    //计算单词数，空格数
    for(int i = 0; i < n; i++)
    {
        if(*(p+i) == ' ')
        {
            length++;
            if(i>0)
            {
                if(*(p+i-1) != ' ')
                    wordCount++;
            }
        }            
    }
    if(*(p+n-1) != ' ')
        wordCount++;
    if(wordCount == 0)
    {
        return;
    }
    else if(wordCount == 1)
    {
        int index = 0;
        for(int i = 0; i < n; i++)
        {
            if(*(p+i) != ' ')
            {

                while(i < n && *(p+i) != ' ')
                {
                    str[index] = *(p+i);
                    i++;
                    index++;
                }
                break;
            }
        }
        for(int i = index; i < n; i++)
        {
            str[index]=' ';
        }
    }
    else
    {
        int whitespacePerWordSpan = length/ (wordCount-1);
        int leftspace = length%(wordCount-1);
        int i =0;
        int j =-1;
        int k;
        //把单词移到字符串的最前面，以一个空格隔开
        for(;i<n;)
            {
                if(*(p+i) == ' ')
                {
                    j++;
                    while(*(p+i) == ' ')
                    {
                        i++;
                    }

                }
                else
                {
                    k = i;
                    while(*(p+i) != ' ' && i < n)
                    {
                        i++;
                    }
                    if(j==-1 || j == k)
                    {
                        j = i;  
                        //i++;
                        continue;
                    }
                    if(k>j)
                {
                    memcpy(str+j,str+k,i-k+1); 
                    for(int m = j+i-k+1; m < i; m++)
                    {
                        str[m] = ' ';
                    }

                    i = j+i-k+1;
                    if(*(p+i) == ' ')
                        j = i-1;
                    else
                        j = i;
                }
            }
        }
        while( j!= -1 && j < n)
        {
            str[j++] = ' ';
        }

        for(i = 0; i < n; i++)
        {
            //移单词，插空格
            if(*(str+i) == ' ')
            {
                if(leftspace > 0)
                {
                    memcpy( str+i+whitespacePerWordSpan+1,str+i+1,n - i - whitespacePerWordSpan-1);
                    for(int m = 0; m < whitespacePerWordSpan; m++)
                    {
                        str[i+1+m]= ' ';
                    }
                    i = i + whitespacePerWordSpan;
                    leftspace--;
                }
                else
                {
                    memcpy( str+i+whitespacePerWordSpan,str+i+1,n - i - whitespacePerWordSpan);
                    for(int m = 0; m < whitespacePerWordSpan-1; m++)
                    {
                        str[i+1+m]= ' ';
                    }    
                    i = i+whitespacePerWordSpan-1;
                }
            }
        }
    }

}