美文网首页
算法复习之字符串(1)

算法复习之字符串(1)

作者: 多了去的YangXuLei | 来源:发表于2017-08-09 16:09 被阅读12次

(1)字符串循环左移 | 字符串全排列(递归,非递归)《本节内容》
(2)KMP算法| BF算法
(3 字符串的最长回文子串|BM算法| 字符串查找

串是有零个或者多个字符组成的有限序列,也叫字符串。电子词典查找单词就是字符串的典型应用

分清空格串和和空串;子串(子序列)和主串;串的顺序存储,链式存储;求串的长度;取第i个位置这些基础操作算法略过

一、字符串循环左移

问题:给定一个字符串S[0...N-1],要求把S的前k 个字符移动到S的尾部,如把字符串“abcdef” 前面的2个字符‘a’、‘b’移动到字符串的尾部,得到新字符串“cdefab”:即字符串循环左移k。

  • 当看到这个题目时候,必然想到暴力法,每次循环左移一位,调用K次,时间复杂度O(kN),空间复杂度O(1)

  • 三次拷贝
    S[0...k] → T[0...k]
    S[k+1...N-1] → S[0...N-k-1]
    T[0...k] →S[N-k...N-1]
    时间复杂度O(N),空间复杂度O(k)

  • 上面都过于粗鲁,学过线代的都知道这个转置,可能不太恰当,理解就好,时间复杂度O(N),空间复杂度O(1):
    如:abcdef
    X=ab X’=ba
    Y=cdef Y’=fedc
    (X’Y’)’=(bafedc)’=cdefab
    是不是很那个奇妙,算法就是要多想想,而不是死记硬背

    void ReverseString(char*,int from,int to){
      while(from < to){
          char t = s[from];
          s[from++] = s[to];
          s[to--] = t;
      }
    }
    void leftRotateString(char*, int n, int m){
          m %= n;
          ReverseString(s,0,m-1);
          ReverseString(s,m,n-1);
          ReverseString(s,0,n-1);
    
    }
    

二、字符串全排列

问题:给定字符串S[0...N-1],设计算法,枚举S的 全排列。

  • 递归
char[] = "1234";
int size = sizeof(str) / sizeof(char);
void Permutation(int from,int to){
    if(from==to){
        for(int i = 0;i <=to;i++){
            cout<<str[i];
        }
        cout<<'\n';
        return;
    }
    for(int i = from; i<=to;i++){
        swap(str[i],str[from]);
        Permutation(from+1,to);
        swap(str[i],str[from]);
    }
} 
int _tmain(int argc, _TCHAR* argv[]){
    Permutaiton(0,size-2);
    return 0;
}

带重复字符的全排列就是每个字符分别与它后面非重复出现的字符交换。即:第i个字符与第j个字符交换时,要求[i,j)中没有与第j个字符相等的数。
代码怎么写?其实在上面基础上加上简单判断一下就行

    for(int i = from; i<=to;i++){
     if(!IsSwap(from,1))
        continue;
    swap(str[i],str[from]);
    Permutation(from+1,to);
    swap(str[i],str[from]);
    }
} 

复杂度计算:
∵f(n) = nf(n-1) + n^2
∵f (n-1)=(n-1)
f(n-2) + (n-1)^2
∴f(n) = n((n-1)f(n-2) + (n-1)^2) + n^2
∵ f(n-2) = (n-2)f(n-3) + (n-2)^2
∴ f(n) = n
(n-1)((n-2)f(n-3) + (n-2)^2) + n(n-1)^2 + n^2
= n
(n-1)(n-2)f(n-3) + n(n-1)(n-2)^2 + n(n-1)^2 + n^2
=.......
< n! + n! + n! + n! + ... + n!
= (n+1)
n!
时间复杂度为O((n+1)!)
注:当n足够大时:n! > n+1

  • 非递归

步骤:后找、小大、交换、翻转——

后找:字符串中最后一个升序的位置i,即:S[k]>Sk+1,S[i]<S[i+1];
查找(小大):S[i+1...N-1]中比Ai大的最小值Sj;
交换:Si,Sj;
翻转:S[i+1...N-1]

代码就不再写了

相关文章

  • 算法复习之字符串(1)

    (1)字符串循环左移 | 字符串全排列(递归,非递归)《本节内容》(2)KMP算法| BF算法(3 字符串的最...

  • 一道关于字符串压缩的面试题

    题目 编写一个算法,实现基本的字符串“压缩”算法,比如对于字符串'abbbbffcccdddcc',经过算法处理之...

  • 文章收藏

    iOS面试题系列之常见算法 排序算法整理 字符串【3】最长回文子串【3】最长无重复子串【1*】字符串转数字【4】K...

  • KMP字符串匹配算法

    KMP字符串匹配算法 先总结一下之前的几种字符串匹配算法 1 BF算法, 最简单的字符串匹配算法, 可以直接使用s...

  • W3Cschool JavaScript脚本算法编程实战 初级脚

    初级脚本算法 1. 翻转字符串算法挑战 实战翻转字符串算法 你可以先把字符串转化成数组,再借助数组的reverse...

  • 字符串匹配算法

    以下为学习 《数据结构与算法之美 -- 字符串匹配》 的记录。 BF算法 即暴力匹配算法,循环遍历匹配。 RK算法...

  • 大厂算法面试之leetcode精讲20.字符串

    大厂算法面试之leetcode精讲20.字符串 视频讲解(高效学习):点击学习[https://xiaochen1...

  • LeetCode基础算法-字符串

    LeetCode基础算法-字符串 LeetCode 算法 字符串 1. 翻转字符串 编写一个函数,其作用是将输入的...

  • 字符串匹配算法

    1.朴素算法2.RK算法3.kmp算法详细讲解:主要在于搜索字符串相对原字符串需要后移多少位.对比字符串与搜索字符...

  • KMP算法文章合集

    字符串的查找:朴素查找算法和KMP算法 暴力匹配算法与KMP算法(串的匹配) 字符串查找算法BF和KMP 字符串匹...

网友评论

      本文标题:算法复习之字符串(1)

      本文链接:https://www.haomeiwen.com/subject/qmqqrxtx.html