用 KMP 算法实现字符串匹配:如果对于一个字符串 A,将 A 的前面任意一部分挪到后边去形成的字符串称为 A 的旋转词。比如 A="12345",A 的旋转词有 12345,23456,34512,45123 和 51234。对于两个字符串 A 和 B,请判断 A 和 B 是否互为旋转词。
给定两个字符串 A 和 B 及他们的长度 lena,lenb,请返回一个 bool 值,代表他们是否互为旋转词。
测试样例:"cdab",4,"abcd",4
返回:true
小技巧:寻找互为旋转词只需要需找 A+A 中有没有 B 即可。
用 KMP 算法匹配字符串时间复杂度为 O(lena+lenb);
- class Rotation {
- public: bool chkRotation(string A, int lena, string B, int lenb) {
- if (lena != lenb) return false;
- string temp = A + A;
- return kmp(temp, B); // write code here } bool kmp(string source,string substr) { vector next=cal_next(substr); int i=0; int j=0; while(i!=source.size()&&j!=substr.size()) { if(source[i]==substr[j]) { ++i; ++j; } else{ if(j==0) ++i; else j=next[j-1]; } } if(j==substr.size()) return true; else return false; } vector cal_next(string substr) { int length=substr.size(); vector next(length,0); for(int i=1;i!=substr.size();++i) { int x=i; while(next[x-1]) { if(substr[i]==substr[next[x-1]]) next[i]=next[x-1]+1; else x=next[x-1]+1; } } return next; }};
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: