考研复试

1. KMP算法

2. const static int MAXN = 105;
   int next_array[MAXN];
   void getNextArray(string pattern) {
       int j = -1;
       next_array[0] = -1;
       for (int i = 1; i < pattern.size(); i++) {
           while (j != -1 && pattern[i] != pattern[j + 1]) {
               j = next_array[j];
           }
           if (pattern[i] == pattern[j + 1]) {
               j++;
           }
           next_array[i] = j;
       }
       return;
   }
   //kmp
   bool KMP(string s, string pattern) {
       int j = -1;
       getNextArray(pattern);
       for (int i = 0; i < s.size(); i++) {
           while (j != -1 && s[i] != pattern[j + 1]) {
               j = next_array[j];
           }
           if (s[i] == pattern[j + 1]) {
               j++;
           }
           if (j == s.size() - 1) {
               return true;
           }
       }
       return false;
   }
   //kmp get number
   int KMP_NUM(string s, string pattern) {
       int j = -1;
       int ans = 0;
       getNextArray(pattern);
       for (int i = 0; i < s.size(); i++) {
           while (j != -1 && s[i] != pattern[j + 1]) {
               j = next_array[j];//不断回退直到j==-1或者s[i]==pattern[j+1]
           }
           if (s[i] == pattern[j + 1]) {//s[i]和patten[j+1]匹配成功
               j++;
           }
           if (j == s.size() - 1) {//s 和pattern完全匹配
               ans++;
               j = next_array[j];
           }
       }
       return ans;
   }

3. 字符串hash

4. //字符串HASH映射
   const int MOD = 1000000007;
   const int P = 10000019;
   long long hashFunc(string str) {
       long long H = 0;
       
       for (int i = 0; i < str.size(); i++) {
           H = (H * P + (str[i] - 'A')) % MOD;
       }
       return H;
   }

5. 最长回文子串--动态规划

6.     const static int MAXN = 1005;
       int dp[MAXN][MAXN];
       
       string longestPalindrome(string s) {
           int L_max=1;
           int start=0;;
           int len =s.size();
           memset(dp,0,sizeof(dp));
           //init
           for(int i=0;i<len;i++){
               dp[i][i]=1;
               if(i<len-1){
                   if(s[i]==s[i+1]){
                       dp[i][i+1]=1;
                       start=i;
                       L_max=2;
                   }                
               }
   
           }
           //状态转移方程
           for(int L=3;L<=len;L++){
               for(int i=0;i+L-1<len;i++){
                   int j=i+L-1;
                   if(s[i]==s[j]&&dp[i+1][j-1]==1){
                       dp[i][j]=1;
                       start=i;
                       L_max=L;
                   }
               }
           }
           return s.substr(start,L_max);
       }

7. 最长回文子序列

8.     const static int MAXN=1005;
       int longestPalindromeSubseq(string s) {
           int dp[MAXN][MAXN]={};
           int len = s.size();
           for(int i=len-1;i>=0;i--){
               dp[i][i]=1;
               for(int j=i+1;j<len;j++){
                       if(s[i]==s[j]){
                           dp[i][j]=dp[i+1][j-1]+2;
                       }else{
                           dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                       }
               }
           }
           return dp[0][len-1];
       }