一.方法介绍

KMP算法—(在主串中寻找匹配的子串)

几个基本前提

  • next数组是从下标为1开始的
  • 模式串也是从下标为0开始的
  • 一个基本的事实是当出现不匹配的字符串时，前面的字符串其实是可以通过匹配比较的字符得出的，关键是如何利用这个信息。
  • 前面匹配了的模式字符串中有最长公共前后缀，则可以将模式串下次要匹配的位置移动到公共前后缀的后面 。
  • 部分匹配表就是对应区域的最长公共前后缀的长度
  • 算出部分匹配表后，在模式串与主串出现不匹配时，模式串最后一次匹配的字符的对应的next值就是模式串下次要和主串上次停留的位置进行匹配的位置，如果在第一个位置就没有匹配，则直接把主串往后移动一位，

前缀、后缀、部分匹配值、部分匹配表

https://www.cnblogs.com/yikecaidechengzhangshi/p/8425572.html-部分匹配表的计算
“前缀”是指除了最后一个字符以外，一个字符串的全部头部组合。
“后缀”是指除了第一个字符以外，一个字符串的全部尾部组合
“部分匹配值”是指“前缀”和“后缀”的最长的共有元素的长度。比如“ABCD”的前缀为[A,AB,ABC],“后缀”为[BCD,CD,D],共有元素的长度是0
“部分匹配表”的实质是，检测字符串的头部和后面的字符串是否有重复 。
模式串部分匹配表的计算

  1. /*
  2. 1.part数组的下标从1开始，s的下标从0开始
  3. 2.part[i]表示第i个字符的部分匹配值，并人为规定part[1]=-1
  4. */
  5. int part[100],i,j;
  6. string s="abababcba"
  7. part[1]=-1;
  8. for (i=2,j=1;i<=s.size();){
  9.     if (j==-2||j==0) {
  10.         part[i]=0;
  11.         j=1;
  12.         i++;
  13.     }else if (j==-1) {
  14.         j=1;
  15.     }
  16.     if (s[i-1]==s[j-1]) {
  17.         part[i]=j;
  18.         i++;
  19.         j++;
  20.     }else{
  21.         j=part[j]-1;
  23.     }
  24.     cout<<"j="<<j<<endl;
  25. }
  26. for (i=1;i<=s.size();i++){
  27.     cout<<part[i]<<endl;
  28. }

部分匹配值和字符不匹配后回退值的关系：
当主串与模式串在某一个位置不匹配时，则在模式串里，该位置的前一个位置 (假设为字符d) 即为最后匹配的字符，从部分匹配值的定义可以知道，以该字符d的部分匹配值+1的位置所在字符，即为主串要进行比较的字符。如图所示
image.png

next数组

next数组的值的定义：
当主串与模式串的某一位字符不匹配时，模式串要回退的位置。也即上面的图中4的值。
由上面的图可知，next[j]的值等于第j位字符前面j-1位字符组成的子串的前后缀重合字符数+1，也即第j-1位字符的部分匹配值+1。

next数组的计算
next的下标从1开始。
模式串的下标从0开始
next[1]=0 （人为规定）
next[j]的值每次最多增加1；并且模式串的最后一位字符不影响next数组的结果。
求法和动态规划算法类似：
边界条件是当i=1时，next[i]=0 ，当i=2时，next[i]=1；
当i>2时，假设next[i-1]==j，则若第i-1位字符和第j位字符相等的话，next[i]=++j;
若不相等的话，则利用next数组的定义，模式串需要回退的地方为j=next[j]。

  1. #include<iostream>
  2. using namespace std;
  3. int GetNext(string s, int length, int next[]){  //length为模式串ch的长度
  4.     next[1]=0;       
  5.     int i=2,j=0;          
  6.     while(i<=length){             
  7.         if(j==0||s[i-2]==s[j-1])   
  8.             next[i++]=++j;                 
  9.         else 
  10.             j=next[j];          
  11.     }   
  12.     for (i=1;i<=length;i++)
  13.         cout<<next[i]<<endl; 
  14. }
  16. int main() {
  17.     string s="abaabcac";
  18.     int next[100];
  19.     GetNext(s,s.size(),next);
  21. }

二.leetcode题

3.无重复字符的最长子串

题目链接

  1. 用(key-value)表的形式，存储字符在字符串s中最近的下标；
  2. 定义当前不重复子串的开始位置为start,结束位置为end，定义当前最大不重复子串的长度为ans;
  3. 在end往后遍历的同时，如果s[end]在(key-value)表中不存在，则加入，如果s[end]在表中存在的话，则取出所对应的下标index，一种情况是该下标index在[start,end]里，则新的start=index+1，另一种情况是index在start左边，这时start仍要保持不变，因此统一一下，也即start=max(index+1,start);然后再更新s[end]在表中的下标。
  4. 每次循环都要利用start,end更新ans。
    1. int lengthOfLongestSubstring(string s) {
    2.      int start=0,end=0,ans=0,i;
    3.      unordered_map<char,int> table;
    4.      for (end=0;end<s.size();end++) {
    5.          if (table.find(s[end])==table.end()) {
    6.              pair<char,int> tmp(s[end],end);
    7.              table.insert(tmp);
    8.          }else {
    9.              start=max(table[s[end]]+1,start);
    10.              table[s[end]]=end;
    11.          }
    12.          ans=max(ans,end+1-start);
    13.      }
    14.      return ans;
    15.  }

5.最长回文子串

题目链接
中心扩散法：
1.对s进行遍历，去找两个相等或者三个对称，一旦找到一个，就开始往两边等长遍历，并更新回文的长度.
2.不需要存储最长回文子串，只需要存储最长回文子串的首尾下标，

205.同构字符串

题目链接
采用单哈希表的方式不能保证“不同字符串不能映射到同一个字符串上”的条件
采用双哈希表的方式则过于繁琐。
于是采用将字符和其位置挂钩，有映射关系的字符，其出现的位置下标必然相同，且ASCII码的码值最大为255，因此申请s_index(256,0),t_index(256,0),并且记录最近一次成功映射后的下标+1(这里是为了与初始化的0相区分开)。

696.计数二进制子串

题目链接
关键点在于对于每一个从0到1或者从1到0的间隔，先统计前面的连续，再统计后面的连续，这种连续段即为需要计数的地方。因为满足条件的，只能是诸如01,0011等这种连续段。

  1.  int countBinarySubstrings(string s) {
  2.         int cur=1,pre=0,i,count=0;
  3.         for (i=1;i<s.size();i++) {
  4.             if (s[i-1]==s[i]) {
  5.                 cur++;
  6.             }else {
  7.                 pre=cur;
  8.                 cur=1;
  9.             }
  10.             if (pre>=cur)
  11.                 count++;
  12.         }
  13.         return count;
  14.     }

227.基本计算器||-(用栈模拟计算)

题目链接
注意几点：
1.不是说把数字和符号都完全压完栈里才进行运算，而是边压栈边弹栈计算，直到栈里面不存在有优先级的运算符。
2.对于负号，可以把负号后面的数以负数的形式压进栈里，保证栈里面全是加法运算；
3.在实际输入过程中，肯定是从左到右入栈。
4.最前面可以加一个’+’，比如3-2+4原则上是+3-2+4，以符号和其后的数字作为一个整体讨论，比如(sign)num
若sign=’+’，则num入栈；
若sign=’-‘，则-num入栈；
若sign=’*’，则取出前面一个数，num与之相乘再入栈
若sign=’/‘，则取出前面一个数，除以num再入栈。
最后对栈进行求和即可(这里也是为什么使用vector的原因，方便求和)

  1. int calculate(string s) {
  2.         vector<int> sta;
  3.         char sign='+';
  4.         int i,num=0;
  5.         for (i=0;i<s.size();i++) {
  6.             if (s[i]>='0'&&s[i]<='9') {
  7.                 num=num*10+(s[i]-'0');
  8.             }
  9.             if (!(s[i]>='0'&&s[i]<='9')&&s[i]!=' '||i==s.size()-1){
  10.                 switch(sign){
  11.                     case '+': sta.push_back(num); break;
  12.                     case '-': sta.push_back(0-num); break;
  13.                     case '*': sta.back()*=num;break;
  14.                     case '/': sta.back()/=num;break;
  15.                 }
  16.                 num=0;
  17.                 sign=s[i];
  18.             }
  19.         }
  20.         return accumulate(sta.begin(),sta.end(),0);
  21.     }

28.实现strStr()

题目链接

  1. int strStr(string haystack, string needle) {
  2.         int nlen=needle.size();
  3.         if (nlen==0)
  4.             return 0;
  5.         vector<int> next(nlen+1,0);
  6.         GetNext(next,needle);
  7.         //KMP
  8.         int i,j,first=-1;
  9.         for (i=0,j=0;i<haystack.size();) {
  10.             if (haystack[i]==needle[j]) {
  11.                 first=i;
  12.                 i++;
  13.                 j++;
  14.                 while (j!=0&&j<nlen) {
  15.                     if (haystack[i]==needle[j]) {
  16.                         i++;
  17.                         j++;
  18.                     }else{
  19.                         first+=j-(next[j+1]-1);
  20.                         j=next[j+1]-1;
  21.                     } 
  22.                 }
  23.                 if (j==nlen)
  24.                     return first;
  25.                 else 
  26.                     j=0;
  27.             }else {
  28.                 i++;
  29.             }
  31.         }
  32.         return -1;
  34.     }
  35.     void GetNext (vector<int> &next, string s) {
  36.         int i=2,j=0;
  37.         next[1]=0;
  38.         while (i<=s.size()) {
  39.             if (j==0||s[i-2]==s[j-1]) {
  40.                 next[i++]=++j;
  41.             }else 
  42.                 j=next[j];
  43.         }
  44.     }

844.比较含退格的字符串-O(1)空间复杂度

题目链接

  1. 这里如果不考虑空间复杂度，那么就先用栈来模拟这个退格的过程，然后把各自新形成的字符串比较即可。
  2. 若要考虑空间复杂度，则关键点在于不存储退格过程中已经确定了的字符，而是直接对其两两比较，然后舍弃，

  3. 下面复用了函数（为了方便表达思想），可以把函数部分拆分合并到主函数中，节省函数调用带来的开销

    1.  int FindNext(string s, int end) {
    2.      int skip=0,i;
    3.      for (i=end;i>=0;i--) {
    4.          if (s[i]=='#')
    5.              skip++;
    6.          else if (skip>0)
    7.              skip--;
    8.          else
    9.              return i;
    10.      }
    11.      return -1;
    12.  }
    13.  bool backspaceCompare(string s, string t) {
    14.      int si=s.size()-1,ti=t.size()-1;
    15.      si=FindNext(s,si);
    16.      ti=FindNext(t,ti);
    17.      while(si!=-1&&ti!=-1) {
    18.          if (s[si]!=t[ti])
    19.              return false;
    20.          si=FindNext(s,si-1);
    21.          ti=FindNext(t,ti-1);
    22.      }
    23.      return si==-1&&ti==-1;
    25.  }

    剑指Offer-19：正则表达式匹配

    题目 请实现一个函数用来匹配包含’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

主串s，模式串p，主串长度slen，模式串长度plen，当前移动到的主串位置i，当前移动到的模式串的位置j。
采用递归法：

  1. bool Rmatch(string s, int si, string p, int pi) {
  2.     if (s.size() == si && p.size() == pi)
  3.         return true;
  4.     if (s.size() != si && p.size() == pi)
  5.         return false;
  6.     if (s.size() == si && p.size() != pi)
  7.         return false;
  8.     if (s[si] == p[pi] || p[pi] == '.')
  9.         return Rmatch(s, si + 1, p, pi + 1);
  10.     if (p[pi] != '*') {
  11.         if (p.size() == pi + 1 || p[pi + 1] != '*')
  12.             return false;
  13.         else
  14.             return Rmatch(s, si, p, pi + 2);
  15.     }
  16.     return Rmatch(s, si, p, pi - 1) || Rmatch(s, si, p, pi + 1);
  17. }

动态规划算法？？？