2.4 字符串的实际应用
2.4.1 字符串包含问题
1）串的模式匹配算法
例1：在字符串中查找子串。给定一个字符串A，要求在A中查找一个子串B。
如主串A=“ababcabcacbab”，要你在A中查找子串（模式串）B=“abcac”。
解答：
（1）使用最基础的算法（BF算法），代码如下：
char＊ strFind(const char ＊string, const char ＊substring){
assert(string!=NULL&& substring!=NULL);
int m=strlen(string);
int n=strlen(substring);
if(m < n)
return NULL;
for (int i=0; i<=m-n; i++){ //时间复杂度为O((m-n+1)＊n)
for (int j=0; j<n; j++){
if (string[i+j]!=substring[j])
break;
}
if (j == n)
return string+i;
}
return NULL;
}
（2）或者使用KMP算法，此时复杂度为O(m+n)。
KMP算法的比较过程是：
第一趟匹配：
第二趟匹配：
直接拿模式串的第1位与主串的第3位（此位上一趟匹配失败）做比较。
第三趟匹配：
直接拿模式串的第2位与主串的第7位（此位上一趟匹配失败）做比较。注意模式串的第一位没有参与比较，这是因为KMP算法已经推得此位必然相等。
第三趟查找模式串成功。
可见KMP算法每当一趟匹配过程中出现字符比较不等时，不需回溯主串，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较，且此时并不一定是拿模式串的第一位继续比较。
下面给出kmp算法的代码，kmp算法的原理及next数组的求法请参考《数据结构》或者《算法导论》等书籍。
int kmp_search(const char ＊ src, int slen, const char ＊ patn, int plen, const
int ＊ nextval, int pos){
int i=pos, j=0;
while (i < slen && j < plen){
if(j == -1 || src[i] == patn[j]){++i;++j;}
else{
j=nextval[j]; /＊当匹配失败时直接用p[j_next]与s[i]比较＊/
}
}
if(j >= plen)
return i-plen;
else
return -1;
}
下面给出计算next数组的函数。
void get_nextval(char const＊ ptrn, int plen, int＊ nextval){
int i=0;nextval[i]=-1; int j=-1;
while(i < plen-1){
if(j == -1 || ptrn[i] == ptrn[j]){++i;++j;nextval[i]=j;}
else
j=nextval[j];
}
}
下列函数为改进了的计算next数组的函数。
void get_nextval(char const＊ ptrn, int plen, int＊ nextval){
int i=0;nextval[i]=-1; int j=-1;
while(i < plen-1){
if(j == -1 || ptrn[i] == ptrn[j]){
++i;
++j;
if(ptrn[i] != ptrn[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}
例2：在长度为M的字符串中，查找长度为N的字符串的最好时间复杂度是 ？（2012·网易）
解答：O(M+N)。使用KMP算法。
2）字符串移位包含问题
例1：给定两个字符串s1和s2，要求判定s2是否能够被s1做循环移位得到的字符串包含。例如，给定s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD，返回false。
解答：
1）以s1=ABCD为例，先分析对s1进行循环移位之后的结果，如下所示：
ABCD->BCDA->CDAB->DABC->ABCD……
假设我们将前面移走的字符串保留下来，则有：
ABCD->ABCDA->ABCDAB->ABCDABC->ABCDABCD
这里，我们可以发现，实际对s1的循环移位得到的字符串实际为s1s1的子字符串。那么我们判断s2是否可以通过s1循环移位得到包含，则只需要判断s1s1中是否含有s2即可，上节中已经给出了这种解法的答案，其中包括使用KMP算法。
其他同类问题：假设有一个函数isSubstring，其功能是判断一个字符串是不是另外一个字符串的子串。现在给你两个字符串s1与s2，请仅使用isSubstring函数判断s2是否能够被s1做循环移位得到的字符串包含。
解答思想是：
如果字符串s1的长度小于s2的长度，则返回0；
否则，连接s1与其自身得到新字符串s1s1，然后判断s2是否是s1s1的子串，若是返回1，若不是返回0。
2）事实上，对于移位包含问题完全可以像普通包含问题一样解决，只不过在指针指向s1末尾元素时，下一操作重新回到s1头元素，这可通过求模操作解决，代码如下：
bool find(const char＊ const src, const char＊ const des){
assert(src!=NULL&&des!=NULL);
int lenSrc=strlen(src);
int lenDes=strlen(des);
if(lenSrc < lenDes)
return false;
int k;
for(int i=0;i<lenSrc;++i){
k=i;
for(int j=0;j<lenDes;j++){
if(src[k++%lenSrc]!=des[j])
break;
}
if(k-i==lenDes)
return true;
}
return false;
}
2.4.2 字符串转换为数字
例1：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，则输出整数345。（2012·亚马逊在线测试、剑指Offer例题）
解答：可以依次扫描字符串，每扫描到一个字符，我们把在之前得到的数字乘以10 再加上当前字符表示的数字。这个思路用循环不难实现。
但整数可能不仅仅只含有数字，还有可能以'+'或者'-'开头，表示整数的正负。因此我们需要把这个字符串的第一个字符做特殊处理。如果第一个字符是'+'号，则不需要做任何操作；如果第一个字符是'-'号，则表明这个整数是个负数。
接着还要考虑非法输入：
1）需要判断这个指针是不是为空。
2）输入的字符串中可能含有不是数字的字符。每当碰到非法的字符，转换停止。
3）溢出问题。若溢出，则返回0。
参考代码：
enum Status {kValid=0, kInvalid};
int g_nStatus=kValid;
int StrToInt(const char＊ str){
g_nStatus=kInvalid;
long long num=0;
if(str != NULL){
const char＊ digit=str;
bool minus=false;
if(＊digit == '+')
digit ++;
else if(＊digit =='-'){
digit ++;
minus=true;
}
while(＊digit != '\0'){
if(＊digit >= '0' && ＊digit <= '9'){
num=num ＊ 10+(＊digit - '0');
if(num > std::numeric_limits<int>::max()){
num=0;
break;
}
digit ++;
}
else{
num=0;
break;
}
}
if(＊digit == '\0'){
g_nStatus=kValid;
if(minus)
num=0- num;
}
}
return num;
}
例2：假设有一个各种字母组成的字符串s1，假设还有另外一个字符串s2，而且s2字符串里的字母数相对少一些。从算法上讲，什么方法能最快地查出s2中的字母是否在s1中都有？（google面试题）
比如，如果是下面两个字符串：
string 1: ABCCDEFGHLMNOPQRS
string 2: DCGSRQPOMC
答案是true，所有在string2里的字母string1也都有，且string2中C出现两次，string1中C也出现了两次。
如果是下面两个字符串：
string 1: ABCCDEFGHLMNOPQRS
string 2: DCGSRQPOZC
答案是false，因为第二个字符串里的Z字母不在第一个字符串里。
解答：注意题意中，当短字符串字母有重复时，长字符串需满足对应字符重复个数大于等于短字符串中相应字符出现的次数。
1）一个方案是先对这两个字符串的字母进行排序，然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m)+O(n log n)次操作，之后的线性扫描需要O(m+n)次操作。
2）对第一个字串进行轮询，把其中的每个字母都放入一个hashtable里(时间复杂度是O(m)，hashtable可以利用数组实现)，字母（当作hashtable的key）每出现一次，则value加1；
然后轮询第二个字串，在hashtable里查询每个字母（key），看能否找到，找到后若其值大于0，则将对应值的value减1，如果找到某个key对应的value为0，说明没有匹配成功，时间复杂度为O(n)。故总的算法时间复杂度为O(n+m)。
3）可以给每个字母分配一个素数，从2开始，以此类推。这样A将会是2，B将会是3，C将会是5，等等。现在遍历第一个字串，把每个字母代表的素数相乘。你最终会得到一个很大的整数。
然后，轮询第二个字符串，用每个字母代表的素数除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，你应该知道它是第一个字串恰好的子集了。此算法需要考虑一个问题，若第一个字符串较长，则最后的乘积可能会超出int的表示范围。此时可以考虑采用大数乘法。
例3：输入两个很大的正数（用C字符串表示），输出它们的乘积，假设不考虑非法输入。
解答：
void multiply(const char ＊a, const char ＊b){
assert(a != NULL && b != NULL);
int i, j, ca, cb, ＊s;
ca=strlen(a);
cb=strlen(b);
s=(int ＊)malloc(sizeof(int)＊(ca+cb)); //分配存储空间
for (i=0;i<ca+cb;i++)
s[i]=0; // 每个元素赋初值0
for (i=0;i<ca;i++)
for (j=0;j<cb;j++)
s[i+j+1]+=(a[i]-'0')＊(b[j]-'0');
for (i=ca+cb-1;i>=0;i--) // 这里实现进位操作
if (s[i]>=10){
s[i-1]+=s[i]/10;
s[i]%=10;
}
char ＊c=(char ＊)malloc((ca+cb)＊sizeof(char));
i=0;
while(s[i]==0) i++; // 跳过头部0元素
for (j=0;i<ca+cb;i++, j++) c[j]=s[i]+'0';
c[j]='\0';
for (i=0;i<ca+cb;i++) cout<<c[i];
cout<<endl;
free(s);
free(c);
}
2.4.3 其他应用
例1：字符串中单词的逆转，即将单词出现的顺序进行逆转。如将“Today is Friday!”逆转为“Friday！is Today”。（2012·百度、人人）
分析：本题也可以作为循环移位来出题，即将“Today is Friday!”循环移7位。
解答：想要不使用额外的空间完成，可以分为两部，首先将字符串全逆转，这样单词出现的顺序得到逆转（“Today is Friday!”逆转为“!yadirF si yadoT”）；然后通过空格分割单词，单词自身进行逆转。
void Reverse(char ＊pb, char ＊pe){
if(pb == NULL || pe == NULL) return;
while(pb < pe){
char tmp=＊pb;//交换pb和pe的内容
＊pb=＊pe;
＊pe=tmp;
pb ++, pe --;
}
}
char＊ ReverseSentence(char ＊pData){
if(pData == NULL) return NULL;
char ＊pBegin=pData;char ＊pEnd=pData;
while(＊pEnd != '\0')
pEnd ++;
pEnd--;//去掉空格
Reverse(pBegin, pEnd);
pBegin=pEnd=pData;
while(＊pBegin != '\0'){
if(＊pBegin == ' '){
pBegin ++;
pEnd ++;
continue;
}
// 反转单词
else if(＊pEnd == ' ' || ＊pEnd == '\0'){
Reverse(pBegin, --pEnd);
pBegin=++pEnd;
}
else
pEnd ++;
}
return pData;
}
例2：删除模式串中出现的字符，如“welcome to asted”，模式串为“aeiou”那么得到的字符串为“wlcm t std"，要求性能最优，字符串中全部为小写字母。（2012·盛大）
解答：最简单的方法是依次遍历每个字符，如是模式串中的一员，则删除。
void fun(char ＊ s){
assert(s != NULL);
int i=0, j=0;
while(s[j] != '\0'){
while(s[j] == 'a' || s[j] == 'e' || s[j] == 'i' || s[j] == 'o' || s[j] == 'u')
j++;
s[i++]=s[j++];
}
s[i]='\0';
}
也可以给每个字母分配一个素数，从2开始，以此类推。这样a将会是2，b将会是3，c将会是5，等等，然后得出“aeiou”的乘积multi，现在遍历字符串s，把每个字母代表的素数除multi，若能整除，则将其删除。
例3：删除字符串开始及末尾的空白符（若干空格），并且把数组中间的多个空格（如果有）符转化为1个。（2012·人民搜索）
解答：
void fun(char ＊ s){
int i=0, j=0;
while(s[j] == ' ') //删除头部的空白符
j++;
int len=strlen(s)-1;
while(s[len] == ' ') len--;//删除尾部的空白符
s[len+1]='\0';
while(s[j] != '\0'){
while(s[j] == ' ')
j++;
/＊将中间连续的空白符变为一个，判断i!=0是为了防止将头部的连续字符变为1个＊/
if(s[j-1] == ' ' && s[j-2] == ' '&&i!=0)
s[i++]=' ';
s[i++]=s[j++];
}
s[i]='\0';
}
例4：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b，假设字符集是ASCII。
解答：由于ASCII字符是一个长度为8的数据类型总共有可能256种可能，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。
参考代码如下：
void FirstNotRepeatingChar(const char＊ pString){
assert(pString != NULL);
const int tableSize=256;
unsigned int hashTable[tableSize];
for(unsigned int i=0; i < tableSize; ++ i)
hashTable[i]=0;
const char＊ pHashKey=pString;
while(＊(pHashKey) != '\0')
hashTable[＊(pHashKey++)] ++;
pHashKey=pString;
while(＊pHashKey != '\0'){
if(hashTable[＊pHashKey] == 1){
printf("%c", ＊pHashKey);
return;
}
pHashKey++;
}
}
其他同类问题还有：
判断一个字符串中所有字符是否都不相同？代码如下：
bool char_set[256] ;
int isUniqueCharString(const char＊ str) {
assert(str != NULL);
int len=strlen(str);
for (int i=0; i < len; ++i){
int val=str[i];
if (char_set[val]) return 0;
char_set[val]=true;
}
return 1;
}
以上算法时间复杂度为O(n)，其中n为字符串的长度。
如果要求在上述算法的基础上进一步降低空间要求，可以使用bit-map（后续章节讲解），如果假设字符串仅包含从'a'到'z'的字符，我们可以将空间需求降低到一个int。
int isUniqueChars(const char＊ str) {
assert(str != NULL);
int checker=0;
int len=strlen(str);
for (int i=0; i < len; ++i) {
int val=str[i] - 'a';
if ((checker & (1 << val)) > 0) return 0;
checker |= (1 << val);
}
return 1;
}
此题若可以改变原始字符串，也可先排序（时间复杂度为O(nlogn)），然后比对相邻字符串是否相等。