文档章节

字符串旋转(str.find()---KMP)

r
 ranjiewen
发布于 2016/11/03 23:52
字数 342
阅读 9
收藏 0
此题旋转带有技巧性,问题转化为常见的问题,熟练STL可以直接用str.find()函数,其是主要想用KMP算法实现字符串的查找算法。。。

//如果对于一个字符串A,将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A = "12345", A的旋转词有"12345", "23451", "34512", "45123"和"51234"。对于两个字符串A和B,请判断A和B是否互为旋转词。
//给定两个字符串A和B及他们的长度lena,lenb,请返回一个bool值,代表他们是否互为旋转词。
//测试样例:
//"cdab", 4, "abcd", 4
//返回:true

#include <iostream>
using namespace std;
#include <string>

class Rotation {
public:
    bool chkRotation(string A, int lena, string B, int lenb) {
        // write code here
        if (A.size()!=B.size())
        {
            return false;
        }
        A = A + A;
        int index = A.find(B); //经典的用KMP算法
        if (index!=-1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};


// KMP Algorithm
public int getIndexOf(String s, String m) {
    if (s.length() < m.length()) {
        return -1;
    }
    char[] ss = s.toCharArray();
    char[] ms = m.toCharArray();
    int si = 0;
    int mi = 0;
    int[] next = getNextArray(ms);
    while (si < ss.length && mi < ms.length) {
        if (ss[si] == ms[mi]) {
            si++;
            mi++;
        }
        else if (next[mi] == -1) {
            si++;
        }
        else {
            mi = next[mi];
        }
    }
    return mi == ms.length ? si - mi : -1;
}

public int[] getNextArray(char[] ms) {
    if (ms.length == 1) {
        return new int[] { -1 };
    }
    int[] next = new int[ms.length];
    next[0] = -1;
    next[1] = 0;
    int pos = 2;
    int cn = 0;
    while (pos < next.length) {
        if (ms[pos - 1] == ms[cn]) {
            next[pos++] = ++cn;
        }
        else if (cn > 0) {
            cn = next[cn];
        }
        else {
            next[pos++] = 0;
        }
    }
    return next;
}

 

本文转载自:http://www.cnblogs.com/ranjiewen/p/5901135.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
[算法总结] 13 道题搞定 BAT 面试——字符串

本文首发于我的个人博客:尾尾部落 1. KMP 算法 谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把...

繁著
2018/09/05
0
0
Python内置字符串操作处理方法详解

Python内置字符串操作处理方法详解 Python字符串各种操作处理的内置方法详细解释如下: str='test Word tt'

木雨山
2012/09/13
87
0
收集常用的Python 内置的各种字符串处理 函数的使用方法

收集常用的Python 内置的各种字符串处理 函数的使用方法 str='python String function' 生成字符串变量str='python String function' 字符串长度获取:len(str) 例:print '%s length=%d' % ......

铂金胖子
2013/02/09
188
0
C++ 使用STL string 实现的split,trim,replace-修订

编辑器加载中... 使用python的时候默认str 对字符串操作支持非常丰富,相信每个C++程序员都自己写过string的strim、split、replace, 写个小工具函数,留着用,以前偷懒,写了好几次,这次总...

晨曦之光
2012/06/07
728
0
C++: string.find()的使用

string.find(substring)返回substring在string中第一次出现的位置,如果没有找到则返回std::string::npos。 示例1 编译运行: 在一些编程语言中,找不到就返回-1,不过这里返回了一个很大的数...

樂天
2016/06/30
788
0

没有更多内容

加载失败,请刷新页面

加载更多

cleanLastUpdated.bat

@echo offrem create by AnXiaole rem 这里写你的仓库路径set REPOSITORY_PATH=C:\Users\AnXiaole\.m2\repositoryrem 正在搜索...for /f "delims=" %%i in ('dir /b /s "%REPO......

安小乐
8分钟前
1
0
操作放大器的用法是什么?

  有区别   1、单级放大的倍数比较有限,一般在100倍以下。放大倍数很大的话,负反馈就比较浅,对于放大倍数的稳定性不利。假如需要放大倍数更高,就不得不动用多级放大电路了。单级放大...

仙溪
10分钟前
2
0
c++ 上传文件 curl

bool uploadFile(std::string url, std::string file, std::string auth) { boost::filesystem::path p(file); CURL *curl; CURLcode res; struct curl_httppost *for......

青黑
16分钟前
2
0
冒泡与插入排序的代码实现

// 冒泡排序,a 表示数组,n 表示数组大小public void bubbleSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 提前退出冒泡循环的标志位 ...

无名氏的程序员
19分钟前
3
0
centos7.6 +mhvtl1.6安装

以前的mhvtl都是在centos6.x,5.x上安装的mhvtl以前版本为1.4,现在最新的1.6出来,可以安装在centos7.6上,下面是安装过程: 1.安装基础包 centos7.6只要能上外网,默认是配置了yun源的,这些...

突突突酱
21分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部