翻转子串(string+KMP+程序猿面试金典)
2023-09-14 09:06:18 时间
翻转子串
- 參与人数:1197时间限制:3秒空间限制:32768K
- 通过比例:35.03%
- 最佳记录:0 ms|8552K(来自 )
题目描写叙述
假定我们都知道很高效的算法来检查一个单词是否为其它字符串的子串。请将这个算法编写成一个函数。给定两个字符串s1和s2。请编写代码检查s2是否为s1旋转而成。要求仅仅能调用一次检查子串的函数。
给定两个字符串s1,s2,请返回bool值代表s2是否由s1旋转而成。字符串中字符为英文字母和空格,区分大写和小写,字符串长度小于等于1000。
測试例子:
"Hello world","worldhello "
返回:false
"waterbottle","erbottlewat"
返回:true
思路:能够用string 的标准库函数,也能够自己写>>KMP算法<<。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; class ReverseEqual { public: /* bool checkReverseEqual(string s1, string s2) { if(s1.size()!=s2.size() || s1.size()==0 || s2.size()==0) return false; s1+=s1; /**用来表示不存在的位置。类型通常是std::container_type::size_type很多容器都提供这个东西。 取值由实现决定。通常是-1。这样做,就不会存在移植的问题了。 if(s1.find(s2)==string::npos)//npos是一个常数 return false; else return true; }*/ void getnext(string &s,vector<int> &next) { int i=0,k=-1; next[0]=-1; while(i<s.size()) { if(k==-1||s[i]==s[k]) { i++; k++; next[i]=k; } else k=next[k]; } } bool kmp(string &t,string &s,vector<int> &next) { // auto iter=next.begin(); // while(iter!=next.end()) // cout<<*iter++<<" "; // cout<<endl; int i=0,j=0; // cout<<t<<" "<<"s1.size()="<<t.size()<<" "<<s<<" "<<"s2.size()="<<s.size()<<endl; int lens=s.size(); int lent=t.size();//查了这么久,为什么会这样 while(i<lent && j<lens)//while(i<t.size() && j<s.size()) { if(j==-1||s[j]==t[i]) { i++; j++; } else j=next[j]; // printf("i=%d\tj=%d\n",i,j); } if(j!=s.size()) return false; else { // s[j]='\0'; // cout<<s<<" "<<j<<endl; return true; } } bool checkReverseEqual(string s1, string s2) { if(s1.size()!=s2.size() || s1.size()==0 || s2.size()==0) return false; vector<int>next(s2.size()+1); getnext(s2,next); s1+=s1; // cout<<s1<<endl; return kmp(s1,s2,next); } }; void Judge(string &s1,string &s2) { ReverseEqual RE; if(RE.checkReverseEqual(s1,s2)) cout<<"true"<<endl; else cout<<"false"<<endl; } int main() { string s1("Hello world"),s2("worldhello"); string s3("water bottle"),s4("er bottlewat"); string s5("bwdyorsngiayocsksyybigrvqxtvhmfyyhmbhhlcenxalcpodllikancwwqbdfrfpcjftfknrekmvdkugdljtlrjcwlwwmswucgebmmsovdezsqtuohnnjjeqyhsnyumngxlgulsiclfrtzzynawgraqctkhrjluykmfujhrwgcgybhaulhmskstwjvgfmofxeuflkkqajialclnlzggccqwdgpkiiobpzgnipliekufylogjrarvxdwslnkwczfltveebzcrjcttxpizhsweeogsixegkwhfwtmtngqjhgkwduahgyyjxihuyxlsksfzpzikdnqvsgyzisnmqgdymkglbtuhjpxhbeybiewrvbdabprqzpvsvdejahfqsnvoijyypmmhpcpbjsukftobgnzxbdltfdfwjk"); string s6("yypmmhpcpbjsukftobgnzxbdltfdfwjDbwdyorsngiayocsksyybigrvqxtvhmfyyhmbhhlcenxalcpodllikancwwqbdfrfpcjftfknrekmvdkugdljtlrjcwlwwmswucgebmmsovdezsqtuohnnjjeqyhsnyumngxlgulsiclfrtzzynawgraqctkhrjluykmfujhrwgcgybhaulhmskstwjvgfmofxeuflkkqajialclnlzggccqwdgpkiiobpzgnipliekufylogjrarvxdwslnkwczfltveebzcrjcttxpizhsweeogsixegkwhfwtmtngqjhgkwduahgyyjxihuyxlsksfzpzikdnqvsgyzisnmqgdymkglbtuhjpxhbeybiewrvbdabprqzpvsvdejahfqsnvoij"); string s7("byyjk"); string s8("yyjkb"); Judge(s1,s2); Judge(s3,s4); Judge(s5,s6); Judge(s7,s8); return 0; }
相关文章
- 银行家算法程序c语言,银行家算法代码c语言编写.doc
- 卡盟网站程序源码,支持无限分站,货源共享「建议收藏」
- 【说站】喝酒神器微信小程序源码 支持流量主解锁多人对战
- python开发mbus程序_Mbus 2019(水表校验程序)V2.1 最新版
- 粒子群优化算法python程序_粒子群算法的具体应用
- 小程序不让用 JS 解释器?那我再肛一次鹅厂
- ❤️Windows下创建【任务计划程序】❤️定期重启服务器中的【JAR包脚本】❤️实现JAR包重启防止卡顿服务超时中断❤️
- 使用C#开发ChatGPT聊天程序
- 开发一个微信小程序(4):查询天气-获取某个城市的实时天气
- 黑色简约多功能工具箱去水印外卖流量主小程序源码
- 车载场景下,小程序如何助力智能化升级
- linux结束程序内存不会马上释放的解决方法详解程序员
- 经常面试到的10个经典的C语言小程序详解编程语言
- 通过SUBMIT方式不同程序间获取ALV数据详解编程语言
- 程序深入 Linux 系统中的驱动程序过滤(linux过滤驱动)
- Linux程序打包实现轻松部署(linux程序打包)
- Linux程序流量监控,助你掌握网络状况!(linux程序流量)
- 解锁Linux系统下Java程序的执行能力(linuxjava执行)
- 优化Redis运行性能的程序实践(redis运行程序)
- PHP经典的给图片加水印程序
- 初级的用php写的采集程序