1）最长不重复子串

使用string和vector<string>

string FindLongestNonRepeatSubstring(string str){    if (str.empty()) return "";    string tmp;//存放临时不重复的子串    vector
     
       svec;//存放所有不重复的子串    int start = 0;//标记每次开始查找子串的下标    int pos = -1; //查找当前字符在子串中的位置下标    tmp.push_back(str[0]);    for (unsigned int i = 1; i < str.size(); ++i)    {        pos = tmp.find(str[i]);        if (pos == -1)        {            tmp.push_back(str[i]);        }        else        {            svec.push_back(tmp);            tmp.clear();            start = start + pos + 1;            i = start;            tmp.push_back(str[i]);        }    }    //vector
      
       ::iterator it = svec.begin();    int maxIndex = 0;    for (unsigned int i = 1; i < svec.size(); ++i)    {        if (svec[i].size() > svec[maxIndex].size())        {            maxIndex = i;        }    }    return svec[maxIndex];}--------------------- 原文：https://blog.csdn.net/yishizuofei/article/details/79059844
      
     

2）字符串的全排列

1 class Solution { 2 public: 3     void dfs(string s,int begin,vector
     
       &result){ 4         if(begin==s.size()-1) 5             result.push_back(s); 6         for(int i=begin;i
      
        Permutation(string str) {16         vector
       
         result;17         dfs(str,0,result);18         sort(result.begin(),result.end());//按照字典序输出19         return result;20     }21 };
       
      
     

 

3）判断字符串A是否是字符串B的子串（字符串模式匹配）- 简单算法(BF)

KMP字符串模式匹配算法是在一个字符串中定位另一个串的高效算法，时间复杂度为O(m+n)。简单匹配算法的时间复杂度为O(m*n)。

int BF(char *A, char *B){    int i = 0, j = 0;    while(A[i] != '\0')    {        if(B[j] != '\0')        {            if(A[i] == B[j])            {                i ++;                j ++;            }            else             {                i = i - j +1;                j = 0;            }        }        if(j == strlen(B))         {            return i - j;        }    }    return -1;}

4）字符串中的最长回文子串-动态规划方法解

假设字符串s的长度为n，建立一个n*n的状态转移矩阵dp。

dp[i][j]表示“以s[i]开始s[j]结尾的子串是否为回文串。如果这个字符串不是回文串，让dp[i][j]=0”；否则为1。

dp[i][j]的递推公式可以这么表述：

（1）当i==j时，dp[i][j]=1。

这很显然，每个单独的字符其实就是回文串。

（2）当 j-i<2：

若s[i]==s[j]，则dp[i][j]=1；否则dp[i][j]=0。

解释：当j-i==1时，若s[i]==s[j]，则s[i]和s[j]可以组成一个长度为2的回文串。若s[i]！=s[j]，显然他们不可能组成回文串，dp[i][j]=0。

（3）当j-i>=2：

若s[i]==s[j]：若dp[i+1][j-1]=1，则dp[i][j]= 1;否则dp[i][j]= 0;

若s[i]！=s[j]：dp[i][j]=0。

解释：如果s[i]==s[j]，表明这个子串有可能是回文串。当去头去尾后它是回文串时，则dp[i][j]= 1。如果去头去尾后不是回文串，那这个子串一定不是回文串，回文串长度只能是0。

若s[i]！=s[j]，显然他们不可能组成回文串，dp[i][j]=0。

 

class Solution {public:    // 最长回文串，使用dp    string longestPalindrome(string str)    {     int n = str.length();    if(n==0) return "";    bool dp[n][n];    fill_n(&dp[0][0],n*n,false);    int left=0,right=0,maxLen = 0;    for(int j=0;j
     
       maxLen))          {              left = i;              right = j;              maxLen = j-i+1;          }      }    }    return str.substr(left,right-left+1);    }};