Số chuỗi con phù hợp trong C ++

Giả sử chúng ta có một chuỗi S và một từ điển các từ, hãy tìm số từ [i] là dãy con của S. Vì vậy, nếu đầu vào là S =“abcde” và từ điển là [“a”, “bb”, “Acd”, “ace”], thì đầu ra sẽ là 3. Bởi vì có ba chuỗi từ trong từ điển, đó là dãy con của S:“a” “acd” và “ace”

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng từ
• tạo một bản đồ m
• cho tôi trong phạm vi từ 0 đến kích thước của từ
  • chèn các từ [i] vào bản đồ m [words [i, 0]] vị trí
• ans:=0
• cho tôi trong phạm vi từ 0 đến kích thước của S
  • char x:=S [i]
  • nếu x có trong bản đồ m, thì
    • temp:=m [x] và xóa m [x]
    • cho j trong phạm vi 0 đến kích thước tạm thời
      • nếu kích thước của temp [j] =1, thì hãy tăng ans lên 1, nếu không thì chèn chuỗi con của temp [j] từ chỉ mục 1 vào m [temp [j, 1]]
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numMatchingSubseq(string S, vector<string>& words) {
      int n = words.size();
      map <char, vector <string> > m;
      for(int i = 0; i < words.size(); i++){
         m[words[i][0]].push_back(words[i]);
      }
      int ans = 0;
      for(int i = 0; i < S.size(); i++){
         char x = S[i];
         if(m.find(x) != m.end()){
            vector <string> temp = m[x];
            m.erase(x);
            for(int j = 0; j < temp.size(); j++){
               if(temp[j].size() == 1){
                  ans++;
               } else {
                  m[temp[j][1]].push_back(temp[j].substr(1));
               }
            }
         }
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   string s = "abcde";
   vector<string> v{"a","bb","acd","ace"};
   cout << ob1.numMatchingSubseq(s, v) << endl;
   return 0;
}

Đầu vào

"abcde"
["a","bb","acd","ace"]
string s = "abcde";
vector<string> v{"a","bb","acd","ace"};

Đầu ra

3