Substring with Concatenation of All Words

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

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

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

C++:
01 typedef vector<int> Vec;
02 vector<int> findSubstring(string S, vector<string> &L)
03 {
04       int n=S.size();
05       int m=L.size();
06       Vec result;
07       if((n==0)||(m==0))
08           return result;
09       int w=L[0].size();
10       map<string, Vec*> t;
11       for(int i=0;i<m;i++){
12           string tmp=L[i];
13           if(t.find(tmp)==t.end()){
14               Vec* v=new Vec;
15               v->push_back(i);
16               t[tmp]=v;
17           }
18           else
19             t[tmp]->push_back(i);
20       }
21       Vec** A=new Vec*[nw+1];
22       for(int i=0;i<=nw;i++){
23           string tmp=S.substr(i,w);
24           if(t.find(tmp)!=t.end()){
25               A[i]=t[tmp];
26           }
27           else
28               A[i]=NULL;
29       }
30       for(int i=0;i<=nm*w;i++){
31           if(A[i]==NULL)
32               continue;
33           bool* check=new bool[m];
34           int cnt=0;
35           for(int j=0;j<m;j++)
36               check[j]=false;
37 
38           for(int j=i;j<=i+(m1)*w;j=j+w){
39               bool flag=false;
40               if(A[j]==NULL)
41                   break;
42               Vec table=*(A[j]);
43               for(int p=0;p<table.size();p++){
44                 int index=table[p];
45                 if(check[index]==false){
46                      check[index]=true;
47                      cnt++;
48                      flag=true;
49                      break;
50                 }
51               }
52               if(flag==false)
53                   break;
54          }
55          if(cnt==m)
56              result.push_back(i);
57       }
58       return result;
59 }
Advertisements
This entry was posted in Hashtable and Map, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s