一个字符串笔试题

crazyinsomnia 发布于 2009/12/23 15:05
阅读 1K+
收藏 0

前段时间同学去起步参加笔试,有道题是这样的:

编写一个确定一字符串在另一字符串中出现次数的算法。例如字符串“this”在字符串“this is my first program. this…”中出现了2次,不要使用库函数(方法)??

当时同学就没有答出来!求解答?

加载中
0
c
captain_black

循环比较..

从长字符串取出一个字符 和 短字符串的第一个字符比较.

匹配的话,长字符串再取下一个字符 和 短字符串的第二个比较.

不匹配的话,短字符串又取回第一个字符 和 长字符串的 下一个字符比较

当短字符串的最后一个字符都匹配了那就出现了一次,计数加1,并且下一个比较 短字符串又取回第一个字符.

一次类推,把长字符串遍历完.就可以算出结果了

全文字表述,可能理解我意思有点难...

0
crazyinsomnia
crazyinsomnia

引用来自“captain_black”的帖子

循环比较..

从长字符串取出一个字符 和 短字符串的第一个字符比较.

匹配的话,长字符串再取下一个字符 和 短字符串的第二个比较.

不匹配的话,短字符串又取回第一个字符 和 长字符串的 下一个字符比较

当短字符串的最后一个字符都匹配了那就出现了一次,计数加1,并且下一个比较 短字符串又取回第一个字符.

一次类推,把长字符串遍历完.就可以算出结果了

全文字表述,可能理解我意思有点难...

理解!感觉可行(还没试过)!不过貌似比较麻烦啊!

0
张江男
张江男

这是在考模式匹配的算法,二楼的算法虽然可行但却不是标准答案

0
y
yygydjkthh

模式匹配算法: http://www.javaeye.com/topic/352954

0
crazyinsomnia
crazyinsomnia

引用来自“yygydjkthh”的帖子

模式匹配算法: http://www.javaeye.com/topic/352954

厉害!java可以实现?

0
Timor君
Timor君

我试着用普通的轮询实现了,不是用模式匹配算法。
C++代码:

int find_substr_num(const TCHAR *str, const TCHAR *substr)  
{
	int str_len = wcslen(str);
	int substr_len = wcslen(substr);

	int num_count = 0;
	int i = 0;
	while(i < str_len)
	{
		int j = 0;
		while(j < substr_len)
		{
			if ( str[i + j] == substr[j])
				j ++;
			else
				break;
		}
		if (j >= substr_len)
		{
			num_count ++;
		}
		i ++;
	}
	return num_count;
}

0
Timor君
Timor君

引用来自“cghy2011”的答案

我试着用普通的轮询实现了,不是用模式匹配算法。
C++代码:

int find_substr_num(const TCHAR *str, const TCHAR *substr)  
{
	int str_len = wcslen(str);
	int substr_len = wcslen(substr);

	int num_count = 0;
	int i = 0;
	while(i < str_len)
	{
		int j = 0;
		while(j < substr_len)
		{
			if ( str[i + j] == substr[j])
				j ++;
			else
				break;
		}
		if (j >= substr_len)
		{
			num_count ++;
		}
		i ++;
	}
	return num_count;
}

我写的真垃圾。。
0
中山野鬼
中山野鬼
这题目已经简单的我不想写了。大学语言课程中应该有这种题目的吧。
0
疯狂的流浪
疯狂的流浪
kmp模式匹配
0
fromdtor
fromdtor
可以递归啊,写出来肯定很直观!
返回顶部
顶部