【牛客网】马三来刷题之串的模式匹配

题目链接：http://www.nowcoder.com/practice/084b6cb2ca934d7daad55355b4445f8a?tpId=49&tqId=29363&rp=1&ru=/ta/2016test&qru=/ta/2016test/question-ranking

串的模式匹配

• 热度指数：977时间限制：3秒空间限制：32768K
• 本题知识点： 编程基础 字符串
•  算法知识视频讲解

题目描述

对于两个字符串A，B。请设计一个高效算法，找到B在A中第一次出现的起始位置。若B未在A中出现，则返回-1。

给定两个字符串A和B，及它们的长度lena和lenb，请返回题目所求的答案。

测试样例： "acbc",4,"bc",2 返回：2

想要简单的通过这道题非常简单，直接用STL的find方法或者Java中IndexOf函数就可以了，但是如果要是面试的时候或者真正在线笔试的时候这么写的话就比较惨了，面试官一定会让你重新用KMP写一遍~  这道题主要考察的是KMP算法的使用。

先来看一下之前说的一行通过的代码：

int findAppearance(string A, int lena, string B, int lenb) {A.find(B); }
另一种借助了string 的substr方法通过的代码，就是简单的从头开始枚举：

int findAppearance(string A, int lena, string B, int lenb) {for(int i=0;i<=lena-lenb;i++){string tmp=A.substr(i,lenb);if(tmp.compare(B)==0)return i;}return -1; }
KMP算法：

vector<int> Getnext(string p){int k=-1;int j=0;vector<int> next(500);int plen=p.size();next[0]=-1;while(j < plen-1){if(k ==-1 || p[k] == p[j]){k++;j++;next[j]=k;}else{k=next[k];}}return next;}int kmpsearch(string s,string p,vector<int> nex){int i=0;int j=0;int slen=s.size();int plen=p.size();while(i < slen && j< plen){if(j == -1 || s[i] == p[j]){i++;j++;}else{j=nex[j];}}if(j == plen){return i-j;}else{return -1;}}int findAppearance(string A, int lena, string B, int lenb) {vector<int> nextB=Getnext(B);return kmpsearch(A,B,nextB);}

每天一道题，保持新鲜感，就这样~

总结

以上是生活随笔为你收集整理的【牛客网】马三来刷题之串的模式匹配的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。