串的练习及一些思考

data_structure

一、strstr

1、题目概述

不调用C/C++的字符串函数，完成StrStr函数：把主串中子串及以后的字符全部返回。例如：主串是“12345678”，子串是“234”，那么函数的返回值就是“2345678”。

2、想法

刚看到这个题目，不由自主的想到了模式匹配，bf以及kmp。
与模式匹配的区别，就在于一个返回的是位置，一个返回的后面的串内容。
还是很好下手的。

由于在匹配里面需要用到字符串长度，先写了strlen函数,返回'/0'之前的数目

//函数返回字符串str 的长度( 即空值结束符之前字符数目)。
 int strlen(char *str)
 {
    int i=0,num=0;
    while (str[i++])
        num++;
    return num;
 }

最初的想法，通过BF算法找到匹配的位置，生成新的字符串，拷贝过去，并返回。如下：

//这是我最初的思想，通过bf算法找到匹配的位置，新生成字符串拷贝过去，并返回
char* strstr(const char *str1, const char *str2)
{
    int m=strlen(str1);
    int n=strlen(str2);
    char *a=new char[m]; 
    int i=0,j=0;
    while (i<m&&j<n)    
    {
        if(str1[i++]==str2[j++]);
        else
        {
            j=0;
            i=i-j+1;
        }
    }
    if (j>=n)
    {
        int k=0;
        int t=i-j;
        while (str1[t])
            a[k++]=str1[t++];
        a[k]='\0';
        return a;
    }
    else
        return "不匹配";
}

但后来想，没有必要拷贝新的空间，就在原始的字符串修改指针位置即可，如下：

//函数返回一个指针，它指向字符串str2 首次出现于字符串str1中的位置，如果没有找到，返回提示。
//当然还是基于BF算法
char* strstr_1( char *str1,  char *str2)
{
    int m=strlen(str1);
    int n=strlen(str2);
    int i=0,j=0;
    while (i<m&&j<n)    
    {
        if(str1[i++]==str2[j++]);
        else
        {
            j=0;
            i=i-j+1;
        }
    }
    if (j>=n)
    {
        return &str1[i-j];
    }
    else
        return "不匹配";
}

这样，就更加方便。测试一下：

    char a[20]="qweqwewqhello";
    char b[10]="he";
    cout<<strstr_1(a,b)<<endl;
    cout<<strstr(a,b)<<endl;

截图如下：

3、c实现

起始对于c语言的函数是怎么实现还是比较感兴趣的，于是搜索了下:

char* strstr(const char*s1,const char*s2)
{
    const char*p=s1;
    const size_t len=strlen(s2);
    for(;(p=strchr(p,*s2))!=0;p++)
    {
        if(strncmp(p,s2,len)==0)
            return(char*)p;
    }
    return(0);
}

这段代码中strchr的作用是查找字符串s中首次出现字符c的位置，strncmp之多比较n个字符，和strcmp类似

二、删除特定字符

用C语言编写一个高效率的函数来删除字符串里的给定字符。这个函数的调用模型如下所示：
void RemoveChars(char str[],char remove[]);
请对设计思路作出解释，并对你解决方案的执行效率进行评估

1、思路

一看到这个题目，第一个想法，就是暴力做，遍历第一个字符串，每次遍历时查找当前字符是否在第二个字符串中出现过

• 出现：删除该字符
• 没有出现过，保留该字符

那么按照这个思路，假设主串长m，子串长n，那么光遍历的时间复杂度就是O(mn);同时如果还需要删除，那么，需要把后面的全部都往前面移动，复杂度为O(m)级别,当然这个效率也还是很高的，特别是在子串长度不大的时候，效率接近线性。

恰巧，前几天在网上看了一篇有意思的文章，内容大概讲的就是，从武侠小说到程序员面试。这篇文章从武侠小说举例，讲述了程序员的几种境界，围绕使用C语言把字母转换成大写，不能使用库函数这个问题展开讨论，其中有这样的一段，很适合我们这里。

char to_upper(char input) 
{
  static char convert_table[] = { ... };
  return convert_table[input];
}

这样会调高程序的效率，在我们这边使用，效果会更加明显，我们预先把26个字母的结果存在数组里面，访问的时候，如果是1，则表明需要去除，否则不需要去除，这样这块就由O(n)变成了O(1)；

然后对于删除，我们可以用以前老师提到过的双指针，一个自始至终记录最后的结果，另一个遍历整个数组，这样，没有额外的开销。

2、实现

代码如下：

bool judge_table[128];
void RemoveChars(char *str,char *remove)
{
    memset(judge_table,false,sizeof(judge_table));
    while(*remove)
        judge_table[*(remove++)]=true;
    char* current;//遍历指针
    char* result;//结果指针
    current=result=str;
    while (*current)
    {
        if (judge_table[*current]==false)//说明这个字符不需要被删除，那么结果指针保存这个字符，并后移，遍历指针也后移
        {
            *result=*current;
            current++;
            result++;
        }
        else//需要被删除，遍历指针后移。
        {
            current++;
        }
    }
    *result='\0';
}

这样，效率控制在O(n)线性级别。

测试结果：

三、颠倒单词的顺序

1、思路

由题目看得到，整体句子被翻转了，而个体单词没有被翻转，如果是java中，用string类型的split方法，分离空格，倒序输出就好了，但是c++没有提供这样的方法。

那么，我们可以先整体倒序，包括各个单词的顺序，然后只需要找准空格，把空格之间的再次调用函数倒序即可，实现思想不难，但码代码的时候，要注意细节。。

2、实现

void reverse(char *start,char *end)
{ 
    char temp;
    while(start<=end)
    {
        temp=*start;
        *start=*end;
        *end=temp;
        start++;
        end--;        
    }
}
void reverseAll(char *str)
{     
    char *start=str;
    char *end=str+strlen(str)-1;
    reverse(start,end); //逆置整个句子
    //当没有到句子的末尾，找到空格，记录每个单词，逆置
    char *tmp=str;
    while (1)
    {
        while (*tmp!=' ')
        {
            tmp++;
            if (*tmp==0)//扫描到末尾，退出函数
            {
                end=tmp-1;
                reverse(start,end);
                return ;
            }
        }
        end=tmp-1;
        reverse(start,end);
        start=++tmp;
    }
}

四、查找包含个数

统计s中包含t的个数

1、分析

这个和模式匹配差不多，就是比模式匹配多了个找个数的过程，所以，我想到了，查到一个后，把剩下的传入继续查找，同时计数器加1，如果传进去的没有找到匹配的字符，那么说明，已经找完了，返回个数就可以了，实现也很简单，和模式匹配算法差不多。

2、代码实现

int countnum(char *str1,char *str2)
{
    int m=strlen(str1);
    int n=strlen(str2);
    int i=0,j=0;
    while (i<m&&j<n)    
    {
        if(str1[i]==str2[j])
        {
            i++;
            j++;
        }
        else
        {
            j=0;
            i=i-j+1;
        }
    }
    if (j>=n)
    {
        num++;
        countnum(&str1[i-j+n],str2);
    }
    else
        return num;
}

测试截图：

3、缺陷

但是有个明显的缺陷，比如主串是"aaaa",字串是"aa",这种情况很难界定。或许为了这种，可以把每次规模只缩小1，应该可以解决这个问题。。