C++에서 list(L)의 모든 단어를 연결하여 만든 string(S)에서 부분 문자열의 시작 인덱스를 찾습니다.

문자열 s가 있고 단어가 거의 없는 또 다른 목록이 있다고 가정합니다. 이 단어는 길이가 같습니다. 단어의 각 단어를 중간 문자 없이 정확히 한 번 연결하는 s에서 부분 문자열의 모든 시작 인덱스를 찾아야 합니다.

따라서 입력이 "wordgoodgoodgoodword"이고 단어가 ["word","good"]이면 출력은 [0,12]가 됩니다. 인덱스 0과 12로 시작하는 부분 문자열이 "wordgood"과 "goodword"이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ok()라는 메서드를 정의하면 문자열 s, 매핑 wordCnt 및 n −

• s를 임시로 복사

• 범위 n에서 s – 1까지의 i에 대해

  • temp의 크기가 0의 배수이면

    • wordCnt에 temp가 없으면 false를 반환합니다.

    • 그렇지 않으면

      • wordCnt[temp]가 1이면 wordCnt에서 temp를 삭제하고 temp를 빈 문자열로 설정

      • 그렇지 않으면 wordCnt[temp]의 값을 1로 줄이고 temp를 빈 문자열로 설정합니다.

  • s[i]

    만큼 온도를 높입니다.

• temp가 wordCnt에 없으면 false를 반환합니다.

• 그렇지 않으면

  • wordCnt[temp]가 1이면 wordCnt에서 temp를 삭제하고 temp를 빈 문자열로 설정

  • 그렇지 않으면 wordCnt[temp]의 값을 1로 줄이고 temp를 빈 문자열로 설정합니다.

• wordCnt의 크기가 0일 때 true를 반환

• 기본 방법에서 다음을 수행하십시오.

• a의 크기가 0이거나 b의 크기가 0이면 빈 배열을 반환합니다.

• map wordCnt를 만들고 b에 있는 문자열의 빈도를 wordCnt에 저장

• ans

  라는 배열을 만듭니다.

• window :=단어 수 x 각 단어의 문자 수

• 문자열의 복사본 하나를 임시로 만들기

• 범위 창에서 i의 경우 – 1

  • 임시 크기가 창으로 나눌 수 있고 ok(temp, wordCnt, size of b[0])를 호출하면

    • i – 창을 ans에 삽입

  • temp에 a[i] 삽입

  • temp> window의 크기인 경우 0, 1

    에서 부분 문자열을 삭제합니다.

• 임시 크기가 창으로 나눌 수 있고 ok(temp, wordCnt, size of b[0])를 호출하면

  • - 창의 크기를 ans

    에 삽입

• 반환

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   bool ok(string s, unordered_map <string, int> wordCnt, int n){
      string temp = "";
      for(int i = 0; i < n; i++){
         temp += s[i];
      }
      for(int i = n; i < s.size(); i++){
         if(temp.size() % n == 0){
            if(wordCnt.find(temp) == wordCnt.end())return false;
            else{
               if(wordCnt[temp] == 1){
                  wordCnt.erase(temp);
                  temp = "";
               } else {
                  wordCnt[temp]--;
                  temp = "";
               }
            }
         }
         temp += s[i];
      }
   if(wordCnt.find(temp) == wordCnt.end())return false;
   else{
      if(wordCnt[temp] == 1){
         wordCnt.erase(temp);
         temp = "";
      } else {
         wordCnt[temp]--;
         temp = "";
      }
   }
   return wordCnt.size() == 0;
}
vector<int>findSubstring(string a, vector<string> &b) {
   if(a.size() == 0 || b.size() == 0)return {};
      unordered_map <string, int> wordCnt;
   for(int i = 0; i < b.size(); i++)wordCnt[b[i]]++;
      vector <int> ans;
      int window = b.size() * b[0].size();
      string temp ="";
      for(int i = 0; i < window; i++)temp += a[i];
      for(int i = window; i < a.size(); i++){
         if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())){
            ans.push_back(i - window);
         }
         temp += a[i];
         if(temp.size() > window)temp.erase(0, 1);
      }
      if(temp .size() % window ==0 && ok(temp, wordCnt, b[0].size()))ans.push_back(a.size() - window);
         return ans;
   }
};
main(){
   vector<string> v = {"word","good"};
   Solution ob;
   print_vector(ob.findSubstring("wordgoodgoodgoodword", v));
}

입력

“wordgoodgoodgoodword”, {"word","good"}

출력

[0, 12, ]