串的练习及一些思考

发表于 | 分类于

一、strstr

1、题目概述

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

2、想法

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//这是我最初的思想，通过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 "不匹配";
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//函数返回一个指针，它指向字符串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 "不匹配";
}

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

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

截图如下：
此处输入图片的描述

3、c实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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语言把字母转换成大写，不能使用库函数这个问题展开讨论，其中有这样的一段，很适合我们这里。

1
2
3
4
5
char to_upper(char input) 
{
  static char convert_table[] = { ... };
  return convert_table[input];
}

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

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

2、实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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，应该可以解决这个问题。。