（原创）数据结构之利用KMP算法解决串的模式匹配问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了（原创）数据结构之利用KMP算法解决串的模式匹配问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含767字，纯文字阅读大概需要2分钟。

内容图文

?

给定一个主串S（长度<=10^6）和一个模式T（长度<=10^5），要求在主串S中找出与模式T相匹配的子串，返回相匹配的子串中的第一个字符在主串S中出现的位置。

输入格式:

输入有两行： 第一行是主串S； 第二行是模式T.

输出格式:

输出相匹配的子串中的第一个字符在主串S中出现的位置。若匹配失败，输出0.

输入样例:

在这里给出一组输入。例如：

aaaaaba
ba

输出样例:

在这里给出相应的输出。例如：

6


解题思路：串的模式匹配有两种：一种是BF算法，一种是KMP算法；
基于这道题给的数据，若用BF算法便会超时，所以我们这道题用KMP算法；
那么问题来了，KMP算法到底怎么用的；简单来讲，就是有两个步骤：
1、求模式串的next数组；
2、进行主串与模式串的匹配；
假设主串和模式串分别为

第一个问题：如何求next数组
 

 
标签：,,,,,,,,	
来源： https://www.cnblogs.com/yewanting/p/10674340.html

	

内容总结

以上是互联网集市为您收集整理的（原创）数据结构之利用KMP算法解决串的模式匹配问题全部内容，希望文章能够帮你解决（原创）数据结构之利用KMP算法解决串的模式匹配问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---