查找字符串(S)中子字符串的起始索引，该字符串是通过将C ++中的列表(L)中的所有单词串联而成的

假设我们有一个字符串s，并且我们还有另一个列表，其中只有几个单词，这些单词的长度相同。我们必须找到s中所有子字符串的起始索引，该索引是每个单词在单词中的连接，且一次没有任何中间字符。

因此，如果输入像“ wordgoodgoodgoodword”，而单词是[“ word”，“ good”]，则输出将是[0,12]。这是因为从索引0和12开始的子字符串是“ wordgood”和“ goodword”。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个名为的方法ok()，它将采用字符串s，映射wordCnt和n-

• 将s复制到临时文件

• 对于范围在n到s的i – 1

• 如果在wordCnt中不存在temp时，则返回false

• 除此以外

• 如果wordCnt [temp]为1，则从wordCnt删除temp，将temp设置为空字符串

• 否则，将wordCnt [temp]的值减小1，将temp设置为空字符串。

• 如果temp的大小是0的倍数，则

• 将温度提高s [i]

• 如果temp不在wordCnt中，则返回false

• 除此以外

• 如果wordCnt [temp]为1，则从wordCnt删除temp，将temp设置为空字符串

• 否则，将wordCnt [temp]的值减小1，将temp设置为空字符串。

• 当wordCnt的大小为0时返回true

• 从主要方法中，执行此操作

• 如果a的大小为0，或b的大小为0，则返回空数组

• 制作一个映射wordCnt，将b中存在的字符串的频率存储到wordCnt中

• 制作一个称为ans的数组

• 窗口：=单词数x每个单词中的字符数

• 将字符串a的一个副本复制到temp

• 对于范围窗口中的我，其大小为– 1

• 将i –窗口插入ans

• 如果临时大小可以被窗口整除并调用ok（temp，wordCnt，b [0]的大小），则

• 在温度中插入a [i]

• 如果temp的大小> window，则从0，1删除子字符串

• 如果临时大小可以被窗口整除并调用ok（temp，wordCnt，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, ]