Problem:

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]

You should return the indices: [0,9]. (order does not matter).

Solution:

由于长度是固定的，因此固定每一个字符串开始的位置，然后向后搜索，查看每一个字符串是否存在，如果不存在i++

C语言源代码（260ms）：

sub不free的话会MLE [cpp] view plain copy typedef struct Node{      char* word;      int times;      struct Node* next;  }data;  #define SIZE 1000  int hash(char* word){      int i=0,h=0;      for(;word[i];i++){          h=(h*31+word[i])%SIZE;      }      return h;  }  int InsertMap(data** map,char* word,int lenw){      int h = hash(word);      if(map[h]==NULL){          map[h]=(data*)malloc(sizeof(data));          map[h]->word=(char*)malloc(sizeof(char)*(lenw+1));          map[h]->times=1;          strcpy(map[h]->word,word);          map[h]->next=NULL;          return 1;      }else{          data* p=map[h];          while(p->next!=NULL){              if(strcmp(p->word,word)==0){                  p->times++;                  return p->times;              }              p=p->next;          }          if(strcmp(p->word,word)==0){              p->times++;              return p->times;          }else{              data* tmp=(data*)malloc(sizeof(data));              tmp->word=(char*)malloc(sizeof(char)*(lenw+1));              tmp->times=1;              strcpy(tmp->word,word);              tmp->next=NULL;              p->next=tmp;              return 1;          }      }  }  int FindMap(data** map,char* sub){      int h = hash(sub);      if(map[h]==NULL){          return -1;      }else{          data* p=map[h];          while(p!=NULL){              if(strcmp(p->word,sub)==0){                  return p->times;              }              p=p->next;          }          return -1;      }  }  char* substring(char* s,int start,int len){      char* sub=(char*)malloc(sizeof(char)*(len+1));      int i=0;      for(;i<len;i++){          sub[i]=s[i+start];      }      sub[i]=0;      return sub;  }  int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {      int lenw=strlen(words[0]),lens=strlen(s),length=wordsSize;      int* res=(int*)malloc(sizeof(int)*(lens-lenw*length+1));      data** map=(data**)malloc(sizeof(data*)*SIZE);      data** tmp=(data**)malloc(sizeof(data*)*SIZE);      int i,j;      for(i=0;i<SIZE;i++){          map[i]=NULL;          tmp[i]=NULL;      }      for(i=0;i<length;i++){          InsertMap(map,words[i],lenw);      }      *returnSize=0;      for(i=0;i<lens-lenw*length+1;i++){          for(j=0;j<SIZE;j++){              if(tmp[j]!=NULL){                  free(tmp[j]);                  tmp[j]=NULL;              }          }          for(j=0;j<length;j++){              char* sub=substring(s,i+j*lenw,lenw);              int mapnum=FindMap(map,sub);              if(mapnum==-1)break;              int num=InsertMap(tmp,sub,lenw);              if(mapnum < num)break;              free(sub);          }          if(j>=length)res[(*returnSize)++]=i;      }      for(i=0;i<SIZE;i++)if(map[i]!=NULL)free(map[i]);      free(map);      return res;  }  

C++源代码（704ms）：

[cpp] view plain copy class Solution {  public:      vector<int> findSubstring(string s, vector<string>& words) {          int lens=s.size(),lenw=words[0].size(),length=words.size();          map<string,int> strmap,tmp;          for(int i=0;i<length;i++){              strmap[words[i]]++;          }          vector<int> res;          for(int i=0;i<lens-lenw*length+1;i++){              tmp.clear();              int j=0;              for(j=0;j<length;j++){                  string sub=s.substr(i+j*lenw,lenw);                  if(strmap.find(sub) == strmap.end())break;                  tmp[sub]++;                  if(strmap[sub] < tmp[sub])break;              }              if(j>=length)res.push_back(i);          }          return res;      }  };