【面试】字符串专题

一，字符串转化

将字符串转换成整数：atoi

将整数转换为字符串：itoa

浮点数与字符串的转换

1）字符串转化为整数

需要注意的地方：

考虑要缜密，注意是否为数字字符；

判断是否为NULL

开头的‘+’‘-’符号的判断

#include "stdio.h"
#include "string.h"
#include "assert.h"

int isDigit(char c)
{
	if(c>='0'&&c<='9')
		return 1;
	else
	    return 0; 
	
} 
int myatoi(const char *str)
{
	assert(str!=NULL);
	int count=strlen(str);
	int result=0;
	
	int sign=1;
	if(str[0]=='-')
    {
    	sign=-1; 
    } 
	else if(str[0]=='+')
	{
		sign=1; 
	} 
	else if(isDigit(str[0])) 
	{
		result=str[0]-'0';
		sign=1; 
	} 
	for(int i=1;i<count;++i)
	{
		assert(isDigit(str[i]));
		
		result=result*10+(str[i]-'0');
	}
	
	return result;
	
	
}
int  main()
{
	printf("%d\n",myatoi("123"));
}

别看一个这么简单的问题，实际要考虑的问题很多。还是看一下glibc的实现吧

#include "stdio.h"
#include "string.h"
#include "assert.h"

#define LONG_MAX 2147483647L 
#define LONG_MIN (-2147483647L-1L)


long int _strtol_internal (const char *nptr, char **endptr, int base, int group)
{
	//注意要使用unsigned long否则会发生溢出，因为long int最多2147483647L ，无法表示2147483648L
	unsigned long int result = 0;
	long int sign = 1;
	//考虑前导空格
	while (*nptr == ' ' || *nptr == '\t')
		++nptr;
	//考虑带有正负号
	if (*nptr == '-')
	{
		sign = -1;
		++nptr;
	}
	else if (*nptr == '+')
		++nptr;
		//如果出现非法输入
	if (*nptr < '0' || *nptr > '9')
	{
		if (endptr != NULL)
			*endptr = (char *) nptr;
		return 0L;
	}
	//考虑进制
	assert (base == 0);
	base = 10;
	if (*nptr == '0')
	{
		if (nptr[1] == 'x' || nptr[1] == 'X')
		{
			base = 16;
			nptr += 2;
		}
		else
			base = 8;
	}
	//防止非法字符 
	while (*nptr >= '0' && *nptr <= '9')
	{
		unsigned long int digval = *nptr - '0';

		//防止溢出，如果溢出了long的表示范围，则置errno 
		if (result > LONG_MAX / 10 || (sign > 0 ? result == LONG_MAX / 10 && digval > LONG_MAX % 10 : 
		          (result == ((unsigned long int) LONG_MAX + 1) / 10 && digval > ((unsigned long int) LONG_MAX + 1) % 10)))
		{
			errno = ERANGE;
			return sign > 0 ? LONG_MAX : LONG_MIN;
		}
		result *= base;
		result += digval;
		++nptr;
	}
	return (long int) result * sign;
}

atoi函数就是这个函数讲第二个参数置为NULL，第三个参数置为10。不知道你注意到了那些空格，越界之类的判断没有。我同学说他写出来的代码最后就被要求加上了这些东西，最后还因此被卡掉了（说是考虑不够慎密，汗）。

2）itoa 函数的实现

char *itoa( int value, char *string,int radix);

先看一看使用：

#include <stdlib.h>
#include <stdio.h>
int main(void)
{
	int number = 12345;
	char string[25];
	itoa(number, string, 10); //按十进制转换
	printf("integer = %d string = %s\n", number, string);
	itoa(number, string, 16); //按16进制转换
	printf("integer = %d string = %s\n", number, string);
	return 0;
} 

整形转化为字符串（这里默认十进制的转换）

//整形转成字符串函数实现
//题目不难，重点考察面试者对问题考虑的全面程度
#include <iostream>
using namespace std;
void itoa_mf(int num,char str[])
{
	int sign = num;
	int i = 0;
	int j = 0;
	char temp[100];
	if(sign < 0)//如果是负数就去掉符号,将-1234转成1234
	{
		num = -num;
	}
	
	do//转成字符串，1234转成"4321"
	{
		temp[i] = num % 10 + '0';
		num /= 10;
		i++;
	}while(num > 0);
	if(sign < 0)//如果是负数的话，加个符号在末尾，如："4321-"
	{
		temp[i++] = '-';
	}
	temp[i] = '\0';
	i--;
	//将temp数组中逆序输入到str数组中
	//将"4321-" ====> "-1234"
	while(i >= 0)
	{
		str[j] = temp[i];
		j++;
		i--;
	}
	//字符串结束标识
	str[j] = '\0';
}
int main()
{
	int a = +123;
	char s[100];
	itoa_mf(a,s);
	cout << s << endl;

}

二，找出字符串的最长子串，要求子串的所有字符相同

例如：str ="sssddddabcdef" 则输出字串为：dddd

#include <stdlib.h>
#include <stdio.h>
#include <string.h> 
char* GetSubstring(char* strSource)
{
  char* strSubstring; //用于保存得到的子串，大小在找到最大子串后再确定，作为返回值
  int nLen;           //源字符串长度
  int nCurPos;        //当前统计字符串的头指针位置(相对于原字符串第一个字符的位置)
  int nCurCount;      //当前统计字符串的长度（有相同字符组成的子字符串）
  int nPos;          //当前最长的子串的头指针位置
  int nCount;        //当前最长的子串的长度

  nLen = strlen(strSource);

  //初始化变量
  nCount = 1;
  nPos = 0;
  nCurCount = 1;
  nCurPos = 0;

  //遍历整个字符串
  for(int i = 1; i < nLen; i++)
  {
    if(strSource[i] == strSource[nCurPos])//如果当前字符与子串的字符相同，子串长度增1
      nCurCount++;
    else  //如果不相同，开始统计新的子串
    {
      if(nCurCount > nCount)//如果当前子串比原先最长的子串长，把当前子串信息(起始位置 + 长度)保留下来
      {
        nCount = nCurCount;
        nPos = nCurPos;
      }
      //长度复值为1，新串的开始位置为i
      nCurCount = 1;
      nCurPos = i;
    }
  }

  //为返回的子串分配空间(长度为nCount,由于要包括字符串结束符\0,故大小要加1)  
  strSubstring = (char*)malloc(nCount + 1);

  //复制子串(用其他函数也可以)
  for(int i = 0; i < nCount; i++)
    strSubstring[i] = strSource[nPos + i];
  strSubstring[nCount] = '\0';

  return strSubstring;
} 

int main()
{
  //输入一个字符串strSource
  char *strSource="absceeeecd"; 
  char* strSubstring = GetSubstring(strSource);

  printf("最长子串为:%s\n长度为：%d",strSubstring,strlen(strSubstring));

  //释放strSubstring
  free(strSubstring);
}

三，求两个字符串的最大公共子字符串

算法时间复杂度：O(n^2)

思想：两个字符串先从第一个字串的第一个字符开始，依次与第二个字串的各个位置字串比较字串

需要记录下最长公共子串在str1中的位置和子串长度

#include<iostream>
#include<cstring>
#include<cassert>
using namespace std;
void findMaxSubstr(const char * str1 , const char * str2 , char * maxSubstr)
{
	assert((str1!=NULL)&&(str2!=NULL));
	assert(maxSubstr!=NULL);
	int maxPos=-1;
	int maxLen=0;
	int k; 
	for(int i=0; i<strlen(str1); i++)
	{
		for(int j=0; j<strlen(str2); j++)
		{
			if(str1[i]==str2[j])
			{
				for(k=1; (str1[i+k]==str2[j+k])&&(str1[i+k]!='\0'); k++)
				             ;
					if(k>maxLen)
					{
						maxPos=i;
						maxLen=k;
					}
			}
		}
	}
	if(maxPos==-1)
	{
		maxSubstr[0]='\0';
	}
	else
	{
		memcpy(maxSubstr , str1+maxPos , maxLen);
		maxSubstr[maxLen]='\0';
	}
}
int main()
{
	char substr[20];
	findMaxSubstr("tianshuai" , "mynameistianshuai" , substr);
	cout<<substr<<endl;
	return 0;
}

四，字符串查找并记录出现次数(普通与kmp)(观察strstr实现)，替代

函数原型：extern char *strstr(char *str1, char *str2);

　　 功能：找出str2字符串在str1字符串中第一次出现的位置（不包括str2的串结束符）

使用：printf("%s",strstr("tianshuai","shuai"));

输出：shuai

实现：

#include "stdio.h"
char *strstr(char *buf, char *sub)
{
	register char *bp;
	register char *sp;

	if (!*sub)
		return buf;
	while (*buf)
   {
		bp = buf;
		sp = sub;
		do 
		{
			if (!*sp)
				return buf;
		} while (*bp++ == *sp++);
		buf += 1;//从下一个位置查找 
	}
	return 0;
}
int main()
{
	printf("%s",strstr("tianshuai","tian")); 
	
} 

求子串的个数只需要略微更改一下就可以

#include "stdio.h"
 
int  strstr(char *buf, char *sub)
{
	register char *bp;
	register char *sp;
    
	int count=0;
	int pos=0; 
	 
	if (!*sub)
		return 0;
	while (*buf)
   {
		bp = buf;
		sp = sub;
		pos=0; 
		do 
		{
			pos++; 
			if (!*sp)
			{
				count++; 
			} 
				//return buf;
		} while (*bp++ == *sp++);
		
		buf += pos;//从下一个位置查找 
	}
	return count;
}
int main()
{
	printf("%d",strstr("tianshuai,tianshuai,tianshui","tian")); 
	
} 

五，解析一个字符串，对字符串中重复出现的字符，只在第一次出现时保留，就是去除重复的字符。

如：abdabbefgf -> abdefg。

根据字符集，建立一个flag数组用来表示是否出现过。

六，给出一个函数来输出一个字符串的所有排列

字典序生成算法问题：字典序

采用next_permutation的算法思想，首先进行一个字符重排序找到按字典序最小的那个字符序列，以它为开端逐步生成所有排列。

七，翻转字符串

参考例子

八，从一个字符串中找出第一个不重复字符

这个也比较简单，类似于5的方法。

九，去除字符串中相邻两个字符的重复

这个应该等价于题目5

十，判断字符串是否含有回文字符子串

枚举字符串的每个位置，作为回文串的中间位置(分偶数奇数两种情况)，如果找到或者找不到都会立即停止，所以总的复杂度不超过O(n)

十一，求最长回文子串

dp

f[i][j] = f[i+1][j-1]

s[i] == s[j]
false s[i] != s[j]

当然这里有一个小小的限定，f[i][j]表示以i,j为首尾的回文串能否构成。然后再找到一个最长的就可以算法，复杂度O(n^2)。实际上这个问题只要枚举回文串的中间位置就可以了，这样实际上就跟10一样了。不过10只需判断是否存在，这需要找到最长的那个。

当然这个问题还有更快的算法：http://richardxx.yo2.cn/articles/kmp和extend-kmp算法.html

------------------------------------------------------引用开始------------------------------------------------------------------------

KMP的另外一个研究方向是Extend KMP（以下简称EK），它是说求得T与所有的S(i)的最长公共前缀（LCP），当然，要控制复杂度在线性以内。

EK我第一次听说是07年baidu校园招聘的笔试题中，它当时的题目是求最长回文子串，当然这是一个耳熟能详，路人皆知可以用Suffix Array很好解决的问题。事后听一个同学说他写了三个算法：Suffix Array，Suffix Tree和EK，当时就不明白EK是什么东西，但又没当面问他，于是这个东西就搁置了很久。知道后来北大的月赛一道题说可以用EK来做，我才终于从03年林希德的文章中开始认识到它，就像KMP一样，这个算法也一下就吸引了我。
设Q(i)表示T和S(i )的后缀的LCP，P(i)表示T和T(i)的后缀的LCP，那么和KMP一样，我们试图用P来求得Q，而P可以用自匹配求得，并且和求Q的过程相似。
我以求P为例简要说明一下。P(2)就直接匹配即可，从i = 3开始，如下：
设k < i，E(k) = k + P(k) - 1，且对所有j < i，有E(k) >= E(j)。
那么，当E(k) >= i时，便可以推知T(i) = T( i - k + 1 )，于是如果P( i - k + 1 ) < E(k) - i + 1，那么P(i) = P( i - k + 1)，否则P(i) >= P( i - k + 1 )，从E(k)开始向后匹配到E(i)，有P(i) = E(i) - i + 1，并且更新 k = i；
还有就是E(k) < i，肯定有E(k) = i - 1，不过这个不重要，重要的是直接从i开始做暴力匹配即可得到E(i)，则P(i) = E(i) - i + 1，更新k = i。
希望我把EK说清楚了，不过这种东西还是自己推导一下有意思，而且记忆周期更长。
最后来罗列下题目。KMP的经典题目是POJ 2185，是要找最小覆盖矩形，如果你认为懂KMP了就去尝试它。EK的经典题是POJ 3376，有一定挑战；当然还有就是上面说的最长回文子串，提醒下用分治＋EK来做是其中一种方法。
嗯，下次打算说下Suffix Array，主要是它那个传说中的线性DC3算法，不过我现在还没把握能不能简单的把它说清楚，姑且认为可以吧。

------------------------------------------------------引用结束------------------------------------------------------------------------

十二，字符串移位包含的问题

题目：给定两个字符串S1与S2，要求判定S2是否能够被通过s1作循环移位得到的字符串包含,例如，给定s1=AABCD与S2=CDAA，返回true;给定s1＝ABCD 与 s2=ACBD，返回false.

直接枚举匹配或者比较s2能否匹配s1s1,以第一个为例也就是说比较AABCDAABCD和CDAA。

十三，strlen strcpy(注意重叠)

#include "stdio.h"
#include "assert.h"
 
char *strcpy (char *dest,const char *src)
{
	assert(src!=NULL); 
    char *temp=dest;
    while((*dest++=*src++)!='\0')
	        ;
    return dest;
}

int main()
{
	char *dest;
	char *src="tianshuai";
    strcpy(dest,src);
	printf("%s",dest); 
} 

上面这个比较复杂，再看FreeBsd的实现

char *strcpy(char * __restrict to, const char * __restrict from)

{

char *save = to;

for (; (*to = *from) != 0; ++from, ++to);

return(save);

}

十四，去掉中文中的英文字符

主要根据字节的第一位进行判断。

十五，求一个字符串中连续出现次数最多的子串

参考博文