字符串问题是面试中经常出现的问题，这类问题有很多，难以不一。下面是几道字符串的题目，网上都能找到解答，自己实现了一下，供网友参考。感觉算法重要的是要有正确的思路，实现起来不是问题。自己一定要多思考，这样收获可能会更多一点。
问题1：找两个字符串的最长公共子串。
具体描述，如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
思路：算法书上一般都有介绍，就是用动态规划的思想。关键是要找到最优子结构性质，这一点比较难。另外一个经常问到的问题“求子数组的最大和”，用的也是动态规划的思想。找两个字符串最长公共子串的核心就是找最优子结构。
设序列X = {x1,x2,…xm}和Y = {y1,y2,…yn}的最长公共子串为Z = {z1,z2,…zk},则
1 若xm= yn且zk=xm=yn, 则Zk-1是Xm-1和Yn-1的最长公共子串
2 若xm!=yn且zk!=xm，则Z是Xm-1和Y的最长公共子串
3 若xm!=yn且zk!=yn，则Z是X和Yn-1的最长公共子串
其中Xm-1= {x1,x2,…,xm-1},Yn-1 = {y1,y2,…,yn-1}Zk-1 = {z1,z2,…zk-1}
有了上述关系，则很容易得到递推的式子。用一个二维数组 R 记录结果，其中Z[i][j]表示Xi和Yj的最长公共子串长度。
（1）如果i = 0或j = 0，Z[i][j] = 0
（2）如果xi和yj相等，Z[i][j] = Z[i-1][j-1] + 1
（3） 如果xi和yj不相等,Z[i][j] = max{Z[i-1][j],Z[i][j-1]}
基本上差不多了，但是题目要求打印最长公共子串，只要用一个数组R记录得到最长公共子串的过程，其中R[i][j]表示Z[i][j]的值是由哪个子问题的解得到的。
参考代码：
//函数功能 ： 打印最长公共子串
//函数参数 ： X为源字符串1，Y为源字符串2，R为记录的过程，row为R的行坐标，col为R的列坐标
//返回值 ： 空
void LCS_Print(const char *X, const char *Y, int **R, int row, int col)
{
if(R[row][col] == 1)
{
LCS_Print(X, Y, R, row-1, col-1);
cout<<X[row-1]; //由Xi-1和Yj-1，再加上Xi或Yj得到
}
else if(R[row][col] == 2)
LCS_Print(X, Y, R, row-1, col); //由Xi-1和Yj得到
else if(R[row][col] == 3)
LCS_Print(X, Y, R, row, col-1); //由Xi和Yj-1得到
else
return;
}
//函数功能 ： 求两个字符串的最大公共子串
//函数参数 ： X为源字符串1，Y为源字符串2
//返回值 ： 最大长度
int LCS(const char *X,const char *Y)
{
if(X == NULL || Y == NULL)
return 0;
int lenX = strlen(X);
int lenY = strlen(Y);
if(lenX == 0 || lenY == 0)
return 0;
int i, j;
int **C = new int *[lenX+1];
int **R = new int *[lenX+1];
//初始化
for(i = 0; i <= lenX; i++)
{
C[i] = new int [lenY+1];
R[i] = new int [lenY+1];
for(j = 0; j <= lenY; j++)
{
C[i][j] = 0;
R[i][j] = 0;
}
}
//开始计算
for(i = 1; i <=lenX; i++)
{
for(j = 1; j <=lenY; j++)
{
if(X[i-1] == Y[j-1]) //字符串的下标从0开始，所以减1，即X1 = X[0] Y1 = Y[0]
{
C[i][j] = C[i-1][j-1] + 1;
R[i][j] = 1; //由Xi-1和Yj-1，再加上Xi或Yj得到
}
else
{
if(C[i-1][j] >= C[i][j-1])
{
C[i][j] = C[i-1][j];
R[i][j] = 2; //由Xi-1和Yj得到
}
else
{
C[i][j] = C[i][j-1];
R[i][j] = 3; //由Xi和Yj-1得到
}
}
}
}
//打印最长公共子串
LCS_Print(X, Y, R, lenX, lenY);
//记录最大长度
int lcs = C[lenX][lenY];
//释放空间
for(i = 0; i <= lenX; i++)
{
delete [] C[i];
delete [] R[i];
}
delete C;
delete R;
R = C = NULL;
return lcs;
}
</div>
问题2：在字符串中删除特定元素
具体描述，输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。
思路：这是字符查找的一个问题，最简单的就是考察第二个字符串的每个字符，然后检查第一个字符串中有没有这个字符，有的话删除。这样的时间复杂度是O(mn)。对于查找，我们容易想到二分查找、散列这些概念。散列的查找是非常快，时间复杂度为O(1)。如果能联想到散列，那么很容易就能给出下面的解法，相信很多人都能想到。需要一个256字节的数组，记录第二个字符串中每个字符的出现情况，0表示未出现，1表示出现。然后遍历第一个字符串，针对每个字符，去查询记录数组，以决定删除与否。
参考代码：
//函数功能 ： 在字符串中删除特定字符
//函数参数 ： pSrc为源字符串，pDel为特定字符集
//返回值 ： 空
void DeleteSpecialChars(char *pSrc, char *pDel)
{
if(pSrc == NULL || pDel == NULL)
return;
int lenSrc = strlen(pSrc);
int lenDel = strlen(pDel);
if(lenSrc == 0 || lenDel == 0)
return;
bool hash[256] = { false };
for(int i = 0; i < lenDel; i++) //建立删除字符的索引
hash[pDel[i]] = true;
//开始删除
char *pCur = pSrc;
while(*pSrc != '\0')
{
if(hash[*pSrc] == false) //不用删除
*pCur++ = *pSrc;
pSrc++;
}
*pCur = '\0';
}
</div>
问题3：左旋转字符串，其实也可以左旋数组
具体描述，定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。
思路：用了一个小技巧，如果旋转的字符串为XY，其中Y是要旋转到X前面的。只要分别将子字符串 X 和 Y 翻转，然后再将整个字符串再做一次翻转即可。STL的一个算法rotate就是用了这个。
参考代码：
//函数功能 ： 将字符串翻转
//函数参数 ： pBegin指向第一个字符，pEnd指向最后一个字符
//返回值 ： 空
void ReverseString(char *pBegin, char *pEnd)
{
if(pBegin == NULL || pEnd == NULL)
return;
while(pBegin < pEnd)
{
//交换字符
char tmp = *pBegin;
*pBegin = *pEnd;
*pEnd = tmp;
//往中间靠拢
pBegin++;
pEnd--;
}
}
//函数功能 ： 将字符串左旋 n 位
//函数参数 ： pSrc为源字符串，n为左旋位数
//返回值 ： 空
void LeftRotateString(char *pSrc, unsigned n)
{
if(pSrc == NULL || n == 0 || n > strlen(pSrc))
return;
int len = strlen(pSrc);
ReverseString(pSrc, pSrc + n - 1);
ReverseString(pSrc + n, pSrc + len - 1);
ReverseString(pSrc, pSrc + len - 1);
}
</div>
问题4：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
思路：这一题不难，因为每个字符只有8位，因此可以用计数法。首先统计字符串中每个字符的出现次数，然后从头遍历字符串，对于当前字符，查询统计表，如果出现的次数为1，则输出该字符即可。
参考代码：
//函数功能 ： 在一个字符串中找到第一个只出现一次的字符
//函数参数 ： pStr为源字符串
//返回值 ： 目标字符
char FirstAppearOnce(char *pStr)
{
if(pStr == NULL)
return '\0'; //未找到返回空字符
int count[256] = {0};
char *pTmp = pStr;
while(*pTmp != '\0') //统计字符串中每个字符出现的次数
{
count[*pTmp]++;
pTmp++;
}
while(*pStr != '\0') //遍历字符串，找到第一个只出现一次的字符
{
if(count[*pStr] == 1)
break;
pStr++;
}
return *pStr; //