寻找子串在主串中的位置

匹配主串与子串的过程
服务器君一共花费了291.470 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

上一篇我们介绍了串的5个基本操作,接下来我们开始了解一下串的一些其它操作吧。

  • 我们先来看这么一个需求。比如主串是 nowamagic.net,子串是 magic,那么如何知道 magic 在主串的第几个字符后的位置呢?

我们思考下算法,然后设计函数。假设主串 s1=nowamagic.net,子串sub=magic。我们要寻找sub在s1中的首个出现位置

  1. 设i用于主串s1中当前位置下标值,j用于子串sub中当前位置下标值。
  2. 首先我们比较s1[1]与sub[1],如果相同的话,可能子串就开始了。
  3. 如果不相等,那么子串仍然是从sub[1]开始,而主串s1则以s1[2]与其比较。
  4. 如果连续出现5次或以上匹配,那么就找到子串了,此时的j必然大于子串长度sub[0]。
/* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
/* 其中,T非空,1≤pos≤StrLength(S)。 */
int Index(String S, String T, int pos)
{
	int i = pos;	/* i用于主串S中当前位置下标值,若pos不为1,则从pos位置开始匹配 */
	int j = 1;				/* j用于子串T中当前位置下标值 */
	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时,循环继续 */
	{
		if (S[i] == T[j]) 	/* 两字母相等则继续 */
      	{
			++i;
         	++j;
      	}
      	else 				/* 指针后退重新开始匹配 */
      	{
         	i = i-j+2;		/* i退回到上次匹配首位的下一位 */
         	j = 1; 			/* j退回到子串T的首位 */
      	}
	}
	if (j > T[0])
		return i-T[0];
	else
		return 0;
}

测试执行代码为:

case 6:
	printf("主串s1为: ");
	StrPrint(s1);
	k=StrAssign(sub,"magic");
	printf("子串sub为: ");
	StrPrint(sub);
	i=Index(s1,sub,1);
	printf("s1的第%d个字母起和sub第一次匹配\n",i);
	break;

程序运行结果:

1.StrAssign 生成串
2.StrLength 求串长
3.StrCompare 串比较
4.Concat 串连接
5.SubString 求子串
6.Index 求子串位置
0.退出
请选择你的操作:
1
串s1为:nowamagic.net

6
主串s1为: nowamagic.net
子串sub为: magic
s1的第5个字母起和sub第一次匹配

完整的程序在后面部分会给出,就不必每篇都贴了。

延伸阅读

此文章所在专题列表如下:

  1. 数据结构里的串是什么东西?
  2. 如何比较串的大小
  3. 串的抽象数据类型ADT
  4. 串的顺序存储结构
  5. 串最基本的5个操作的C实现
  6. 寻找子串在主串中的位置
  7. 如何在串中插入串
  8. 如何在串中删除特定长度的子串
  9. 字符串中的子串替换
  10. 题外话:谈谈malloc()和free()

本文地址:http://www.nowamagic.net/librarys/veda/detail/2422,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2422

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《Head First设计模式(中文版)》 弗里曼 (作者), 等 (作者)

《Head First设计模式》(中文版)共有14章,每章都介绍了几个设计模式,完整地涵盖了四人组版本全部23个设计模式。前言先介绍这本书的用法;第1章到第11章陆续介绍的设计模式为Strategy、Observer、Decorator、Abstract Factory、Factory Method、Singleton,Command、Adapter、Facade、TemplateMethod、Iterator、Composite、State、Proxy。最后三章比较特别。第12章介绍如何将两个以上的设计模式结合起来成为新的设计模式(例如著名的MVC模式),作者称其为复合设计模式(这是作者自创的名称,并非四人组的标准名词)。

更多计算机宝库...